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.