Computational Complexity Conference

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:55Opening 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:00Coffee Break
11:00 Invited talk: Fine-grained derandomization

Dean Doron

12:00-13:30Boxed 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:30Coffee 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:40Short 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:00Business meeting

Thursday, July 21

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:00Coffee Break
11:00 Invited talk: LTCs and quantum codes

Gilles Zemor

12:00-13:30Boxed 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:30Coffee 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:40Short 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:30Conference reception

Friday, July 22

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:00Coffee Break
11:00 Invited talk: Meta-Complexity

Rahul Santhanam

12:00-13:30Boxed 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:30Coffee 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:00Rump Session

Saturday, July 23

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:15Short 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:30Short 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

Organized by:


In cooperation with: