CCC 2024 Accepted Papers
A Technique for Hardness Amplification Against AC^0
Streaming Zero-Knowledge Proofs
Solving Unique Games over Globally Hypercontractive Graphs
Derandomizing Logspace with a Small Shared Hard Drive
Explicit Time and Space Efficient Encoders Exist Only With Random Access
The Entangled Quantum Polynomial Hierarchy Collapses
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries
Lifting dichotomies
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
Linear-Size Boolean Circuits for Multiselection
A subquadratic upper bound on sum-of-squares compostion formulas
Hard submatrices for non-negative rank and communication complexity
Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture
Quantum Automating TC⁰-Frege Is LWE-Hard
A Strong Direct Sum Theorem for Distributional Query Complexity
Local Enumeration and Majority Lower Bounds
Small bias is no cheaper than uniformity
Information Dissemination via Broadcasts in the Presence of Adversarial Noise
Lower Bounds for Set-Multilinear Branching Programs
Public-key pseudoentanglement and the hardness of learning ground state entanglement structure
Depth-d Frege systems are not automatable unless P=NP
Exponential Separation Between Powers of Regular and General Resolution Over Parities
Distribution-Free Proofs of Proximity
On the degree of polynomials computing square roots mod p
Dimension Independent Disentanglers from Unentanglement and Applications
Baby PIH: Parameterized Inapproximability of Min CSP
Finding missing items requires strong forms of randomness
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity
The Computational Advantage of MIP* Vanishes in the Presence of Noise
Low-depth algebraic circuit lower bounds over any field
$\mathsf{BPL}\subseteq\textsf{L-AC}^1$
Failure of Feasible Disjunction Property for k-DNF Resolution and NP-hardness of Automating It
Search-to-Decision Reductions for Kolmogorov Complexity
Finer-Grained Hardness of Kernel Density Estimation
Gap MCSP is not (Levin) NP-complete in Obfustopia