CCC'22 Accepted Papers
The Approximate Degree of Bipartite Perfect Matching
On the Satisfaction Probability of k-CNF Formulas
Hitting Sets for Regular Branching Programs
Linear Branching Programs and Directional Affine Extractors
Quantum search-to-decision reductions and the state synthesis problem
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
ell_p-Spread and Restricted Isometry Properties of Sparse Random Matrices
Trading Time and Space in Catalytic Branching Programs
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
New Near-Linear Time Decodable Codes Closer to the GV Bound
Certifying solution geometry in random CSPs: counts, clusters and balance
On Efficient Noncommutative Polynomial Factorization via Higman Linearization
A better-than-3log(n) depth lower bound for De Morgan formulas with restrictions on top gates
The plane test is a local tester for Multiplicity Codes
Pseudorandom Generators, Resolution and Heavy Width
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity
Nisan--Wigderson generators in Proof Complexity: New lower bounds
High-Dimensional Expanders from Chevalley Groups
The composition complexity of majority
The Acrobatics of BQP
Random restrictions and PRGs for PTFs in Gaussian Space
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
Finding Errorless Pessiland in Error-Prone Heuristica
Symmetry of Information from Meta-Complexity
Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
On Randomized Reductions to the Random Strings
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
Further Collapses in TFNP
Improved Pseudorandom Generators for AC^0 Circuits
Characterizing Derandomization Through Fine-Grained Hardness of Levin-Kolmogorov Complexity
On One-way Functions from NP-Complete Problems
Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle
Improved Low-Depth Set-Multilinear Circuit Lower Bounds
Organized by:
In cooperation with:
