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