CCC 2022 Conference
I have a private plane. But I fly commercial when I go to environmental conferences—Arnold Schwarzenegger
Computational Complexity Conference CCC is about to happen:
July 20—23, Philadelphia, PA, USA
It is an annual conference on the inherent difficulty of computational problems in terms of the resources they require.
Ryan Williams just sent out a request on behalf of CCC: The travel allowances for CCC are available for students from US universities. The deadline for applying is June 8. Here is the link.
Accepted Papers
Here is a list of the accepted papers with pointers to versions of the 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 Pudlak 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. l_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
- Pavel Hubacek. Snakes on Ladders: On the Complexity of the Parity Argument on Directed Cycles
- 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 Sebastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
- Mika Goos, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere and Ran Tao. Further Collapses in TFNP
- Xin Lyu. Improved Pseudorandom Generators for
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
Open Problems
Is this list with pointers helpful? It took a few minutes to form this list—had to add the pointers.



It doesn’t seem like the link for Hirahara’s work, “Symmetry of Information from Meta-Complexity,” actually goes to a paper
It was helpful, thank you for adding the pointers!