CCC'22 Program
Schedule The slots for contributed talks are 30 minutes (including 5 minutes for questions and changing speakers). In addition there are invited talks on Wednesday, Thursday and Friday which are one hour each. The business meeting is on Wednesday evening, the conference reception on Thursday evening and a rump session (where you can discuss your favorite open problems!) on Friday evening. All the talks and the business meeting will be held in the Wu and Chen Auditorium, located inside the Levine Hall, 3330 Walnut Street. The reception will be held in the foyer of the Levine Hall.
All times below are in Eastern Daylight Time (EDT).
Proceedings: The official version will be openly accessible via LIPIcs.
Pre-recorded videos of talks on these papers are available via this link.
Wednesday, July 20
| 8:30 | Breakfast |
| 8:55 | Opening remarks |
| 9:00 |
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan |
| 9:30 |
New Near-Linear Time Decodable Codes Closer to the GV Bound
Guy Blanc and Dean Doron |
| 10:00 |
The plane test is a local tester for Multiplicity Codes
Dan Karliner, Roie Salama and Amnon Ta-Shma |
| 10:30-11:00 | Coffee Break |
| 11:00 |
Invited talk: Fine-grained derandomization
Dean Doron |
| 12:00-13:30 | Boxed Lunch (provided) |
| 13:30 |
Derandomization from Time-Space Tradeoffs (co-winner Best student paper) Oliver Korten |
| 14:00 |
Nisan--Wigderson generators in Proof Complexity: New lower bounds
Erfan Khaniki |
| 14:30 |
Pseudorandom Generators, Resolution and Heavy Width
Dmitry Sokolov |
| 15:00-15:30 | Coffee break |
| 15:30 |
Hitting Sets for Regular Branching Programs
Andrej Bogdanov, William Hoza, Gautam Prakriya and Edward Pyne |
| 16:00 |
Improved Pseudorandom Generators for AC^0 Circuits (co-winner Best student paper)
Xin Lyu |
| 16:30-16:40 | Short break |
| 16:40 |
Random restrictions and PRGs for PTFs in Gaussian Space
Zander Kelley and Raghu Meka |
| 17:10 |
Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs
Louis Golowich and Salil Vadhan |
| 18:00 | Business meeting |
Thursday, July 21
| 8:30 | Breakfast |
| 9:00 |
Quantum search-to-decision reductions and the state synthesis problem
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao and Henry Yuen |
| 9:30 |
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
Nikhil Bansal, Makrand Sinha and Ronald de Wolf |
| 10:00 |
The Acrobatics of BQP (winner - Best paper award)
Scott Aaronson, Devon Ingram and William Kretschmer |
| 10:30-11:00 | Coffee Break |
| 11:00 |
Invited talk: LTCs and quantum codes
Gilles Zemor |
| 12:00-13:30 | Boxed Lunch (provided) |
| 13:30 |
On One-way Functions from NP-Complete Problems Yanyi Liu and Rafael Pass |
| 14:00 |
Finding Errorless Pessiland in Error-Prone Heuristica
Shuichi Hirahara and Mikito Nanashima |
| 14:30 |
Characterizing Derandomization Through Fine-Grained Hardness of Levin-Kolmogorov Complexity
Yanyi Liu and Rafael Pass |
| 15:00-15:30 | Coffee break |
| 15:30 |
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
Karthik C. S. and Subhash Khot |
| 16:00 |
Certifying solution geometry in random CSPs: counts, clusters and balance
Jun-Ting Hsieh, Sidhanth Mohanty and Jeff Xu |
| 16:30-16:40 | Short break |
| 16:40 |
High-Dimensional Expanders from Chevalley Groups
Ryan O'Donnell and Kevin Pratt |
| 17:10 |
The composition complexity of majority
Victor Lecomte, Prasanna Ramakrishnan and Li-Yang Tan |
| 18:00-19:30 | Conference reception |
Friday, July 22
| 8:30 | Breakfast |
| 9:00 |
The Approximate Degree of Bipartite Perfect Matching
Gal Beniamini |
| 9:30 |
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
Amol Aggarwal and Josh Alman |
| 10:00 |
ell_p-Spread and Restricted Isometry Properties of Sparse Random Matrices
Venkatesan Guruswami, Peter Manohar and Jonathan Mosheiff |
| 10:30-11:00 | Coffee Break |
| 11:00 |
Invited talk: Meta-Complexity
Rahul Santhanam |
| 12:00-13:30 | Boxed Lunch (provided) |
| 13:30 |
On Randomized Reductions to the Random Strings Michael Saks and Rahul Santhanam |
| 14:00 |
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
Lijie Chen, Jiatu Li and Tianqi Yang |
| 14:30 |
A better-than-3log(n) depth lower bound for De Morgan formulas with restrictions on top gates Ivan Mihajlin and Anastasia Sofronova |
| 15:00-15:30 | Coffee break |
| 15:30 |
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity
Halley Goldberg, Valentine Kabanets, Zhenjian Lu and Igor C. Oliveira |
| 16:00 |
Symmetry of Information from Meta-Complexity
Shuichi Hirahara |
| 16:30 |
On the Satisfaction Probability of k-CNF Formulas
Till Tantau |
| 18:00-19:00 | Rump Session |
Saturday, July 23
| 8:30 | Breakfast |
| 9:00 |
On Efficient Noncommutative Polynomial Factorization via Higman Linearization
Vikraman Arvind and Pushkar Joglekar |
| 9:30 |
Improved Low-Depth Set-Multilinear Circuit Lower Bounds
Deepanshu Kush and Shubhangi Saraf |
| 10:00-10:15 | Short coffee break |
| 10:15 |
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
Nutan Limaye, Srikanth Srinivasan and Sebastien Tavenas |
| 10:45 |
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
Harm Derksen, Visu Makam and Jeroen Zuiddam |
| 11:15-11:30 | Short coffee break |
| 11:30-12:00 |
Trading Time and Space in Catalytic Branching Programs Ian Mertz and James Cook |
| 12:00-12:30 |
Linear Branching Programs and Directional Affine Extractors
Svyatoslav Gryaznov, Pavel Pudlak and Navid Talebanfard |
| 12:30-14:00 | Boxed Lunch (provided) |
| 14:00 |
Further collapses in TFNP Mika Goos, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere and Ran Tao |
| 14:30 |
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
Sarah Bordage, Mathieu Lhotel, Jade Nardi and Hugues Randriam |
| 15:00 |
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
Gal Arnon, Alessandro Chiesa and Eylon Yogev |
| 15:30 | Closing remarks |
