Computational Complexity Conference
CCC'22 Accepted Papers

CCC'22 Accepted Papers

Gal Beniamini. The Approximate Degree of Bipartite Perfect Matching
Till Tantau. On the Satisfaction Probability of k-CNF Formulas
Andrej Bogdanov, William Hoza, Gautam Prakriya and Edward Pyne. Hitting Sets for Regular Branching Programs
Svyatoslav Gryaznov, Pavel Pudlák and Navid Talebanfard. Linear Branching Programs and Directional Affine Extractors
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao and Henry Yuen . Quantum search-to-decision reductions and the state synthesis problem
Karthik C. S. and Subhash Khot . Almost Polynomial Factor Inapproximability for Parameterized k-Clique
Venkatesan Guruswami, Peter Manohar and Jonathan Mosheiff . ell_p-Spread and Restricted Isometry Properties of Sparse Random Matrices
Ian Mertz and James Cook . Trading Time and Space in Catalytic Branching Programs
Harm Derksen, Visu Makam and Jeroen Zuiddam . Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
Guy Blanc and Dean Doron. New Near-Linear Time Decodable Codes Closer to the GV Bound
Jun-Ting Hsieh, Sidhanth Mohanty and Jeff Xu . Certifying solution geometry in random CSPs: counts, clusters and balance
Vikraman Arvind and Pushkar Joglekar . On Efficient Noncommutative Polynomial Factorization via Higman Linearization
Ivan Mihajlin and Anastasia Sofronova . A better-than-3log(n) depth lower bound for De Morgan formulas with restrictions on top gates
Dan Karliner, Roie Salama and Amnon Ta-Shma . The plane test is a local tester for Multiplicity Codes
Dmitry Sokolov. Pseudorandom Generators, Resolution and Heavy Width
Halley Goldberg, Valentine Kabanets, Zhenjian Lu and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity
Erfan Khaniki. Nisan--Wigderson generators in Proof Complexity: New lower bounds
Ryan O'Donnell and Kevin Pratt . High-Dimensional Expanders from Chevalley Groups
Victor Lecomte, Prasanna Ramakrishnan and Li-Yang Tan. The composition complexity of majority
Scott Aaronson, Devon Ingram and William Kretschmer . The Acrobatics of BQP
Zander Kelley and Raghu Meka. Random restrictions and PRGs for PTFs in Gaussian Space
Amol Aggarwal and Josh Alman . Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
Lijie Chen, Jiatu Li and Tianqi Yang . Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
Gal Arnon, Alessandro Chiesa and Eylon Yogev . Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
Shuichi Hirahara and Mikito Nanashima . Finding Errorless Pessiland in Error-Prone Heuristica
Shuichi Hirahara. Symmetry of Information from Meta-Complexity
Louis Golowich and Salil Vadhan . Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs
Nikhil Bansal, Makrand Sinha and Ronald de Wolf. Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings
Sarah Bordage, Mathieu Lhotel, Jade Nardi and Hugues Randriam . Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi and Srikanth Srinivasan . Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere and Ran Tao. Further Collapses in TFNP
Xin Lyu. Improved Pseudorandom Generators for AC^0 Circuits
Yanyi Liu and Rafael Pass . Characterizing Derandomization Through Fine-Grained Hardness of Levin-Kolmogorov Complexity
Yanyi Liu and Rafael Pass . On One-way Functions from NP-Complete Problems
Oliver Korten. Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle
Deepanshu Kush and Shubhangi Saraf . Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Organized by:


In cooperation with: