Reading Group paper suggestions – Summer 2024




Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes

https://arxiv.org/abs/2212.03328



Quartic Samples Suffice for Fourier Interpolation

https://arxiv.org/abs/2210.12495


Certified Hardness vs. Randomness for Log-Space

https://arxiv.org/abs/2303.16413



Explicit orthogonal and unitary designs

https://arxiv.org/abs/2310.13597



SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

https://eccc.weizmann.ac.il/report/2023/165/


Strong Bounds for 3-Progressions

https://arxiv.org/abs/2302.05537


On Pseudolinear Codes for Correcting Adversarial Errors

https://arxiv.org/abs/2307.05528



On the Power of Adaptivity for Function Inversion

https://eccc.weizmann.ac.il/report/2024/054/



Local Correction of Linear Functions over the Boolean Cube

https://eccc.weizmann.ac.il/report/2024/056/



Computing a Fixed Point of Contraction Maps in Polynomial Queries

https://eccc.weizmann.ac.il/report/2024/057/



Planted Clique Conjectures Are Equivalent

https://eccc.weizmann.ac.il/report/2024/058/



Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective

https://eccc.weizmann.ac.il/report/2024/077/



Does Prior Knowledge Help Detect Collisions?

https://eccc.weizmann.ac.il/report/2023/207/

Sampling, Flowers and Communication

https://eccc.weizmann.ac.il/report/2023/196/



Derandomized Squaring: An Analytical Insight into Its True Behavior

https://eccc.weizmann.ac.il/report/2023/183/



A Technique for Hardness Amplification Against AC0

https://eccc.weizmann.ac.il/report/2023/176/



On the Rational Degree of Boolean Functions and Applications

https://eccc.weizmann.ac.il/report/2023/154/



A Tight Lower Bound of  (logn) for the Estimation of the Number of Defective Items

https://eccc.weizmann.ac.il/report/2023/141/



Asymptotically-Good RLCCs with (logn)2+o(1) Queries

https://eccc.weizmann.ac.il/report/2023/110/



Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

https://eccc.weizmann.ac.il/report/2023/098/



Efficient Interactive Proofs for Non-Deterministic Bounded Space

https://eccc.weizmann.ac.il/report/2023/097/



A High Dimensional Goldreich-Levin Theorem

https://eccc.weizmann.ac.il/report/2023/088/



Hardness Self-Amplification: Simplified, Optimized, and Unified
https://eccc.weizmann.ac.il/report/2023/026/


The Complexity of the Shortest Vector Problem
https://eccc.weizmann.ac.il/report/2022/170/


A subquadratic upper bound on sum-of-squares compostion formulas

https://eccc.weizmann.ac.il/report/2024/026/



Locality Bounds for Sampling Hamming Slices

https://eccc.weizmann.ac.il/report/2024/031/



Randomness Extractors in AC0 and NC1: Optimal up to Constant Factors

https://eccc.weizmann.ac.il/report/2024/040/