Computational Complexity Conference

CCC'19 Program

Schedule: Except for the first, the slots for contributed talks are 30 minutes long, and include five minutes for questions and changing speakers. The first slot on Thursday is shared by two contributed papers and is one hour long, including the time for questions.

There are invited talks on Friday and Saturday, 9:00–10:00. There is also a reception on Wednesday at 19:30, a business meeting on Thursday at 17:45, and a rump session on Friday at 17:45. Light breakfast is provided; lunch and dinner are on your own.

Venue: All activities except the reception take place at the Rutgers University College Avenue Campus, Rutgers Academic Building, Room 2225, 15 Seminary Place, New Brunswick, NJ. The reception takes place at Panico's, 94 Church Street, New Brunswick, NJ.

Slides and Videos: Click the word "slides" in the program to see the presentations that the authors agreed to post on this website. Videos of the invited talks can be viewed by clicking on the word "video".

Proceedings: The official version is openly accessible via LIPIcs.

Wednesday, July 17

19:30–22:00

Opening Reception

Thursday, July 18

8:30	Breakfast
9:00	Limits on the Universal Method for Matrix Multiplication Josh Alman and Barriers for Fast Matrix Multiplication from Irreversibility (slides) Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
10:00	Break
10:30	Fourier and Circulant Matrices are Not Rigid (slides) Zeev Dvir and Allen Liu
11:00	Typically-Correct Derandomization for Small Time and Space (slides) William Hoza
11:30	A Time-Distance Trade-Off for GDD with Preprocessing---Instantiating the DLW Heuristic Noah Stephens-Davidowitz
12:00	Almost Optimal Distribution-Free Junta Testing (slides) Nader Bshouty
12:30	Lunch
14:00	Average-Case Quantum Advantage with Shallow Circuits (slides) François Le Gall
14:30	Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion Matthew Coudron and Aram Harrow
15:00	Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision Matthew Coudron and William Slofstra
15:30	Break
16:00	Equality Alone Does not Simulate Randomness Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals
16:30	Optimality of Linear Sketching under Modular Updates (slides) Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev
17:00	Optimal Separation and Strong Direct Sum for Randomized Query Complexity (slides) Joshua Brody and Eric Blais
17:30	Short Break
17:45	Business meeting

Friday, July 19

8:30	Breakfast
9:00	Invited Talk Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning (abstract, slides, video) Ran Raz Can one prove unconditional lower bounds on the number of samples needed for learning, under memory constraints? A recent line of works shows that for a large class of learning problems, any learning algorithm requires either a memory of super-linear size or a super-polynomial number of samples. For example, any algorithm for learning parities of size n, from a stream of samples, requires either a memory of quadratic size or an exponential number of samples. A main message of these works is that for some learning problems, access to a relatively large memory is crucial. I will give a short introduction to the topic and will present, in the second half of the talk, some of the proof ideas.
10:00	Break
10:30	Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas (slides) Dean Doron, Pooya Hatami, and William Hoza
11:00	Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions Xin Li
11:30	Fourier Bounds and Pseudorandom Generators for Product Tests Chin Ho Lee
12:00	Simple and Efficient Pseudorandom Generators from Gaussian Processes (slides) Eshan Chattopadhyay, Anindya De, and Rocco Servedio
12:30	Lunch
14:00	Time-Space Lower Bounds for Two-Pass Learning (slides) Sumegha Garg, Ran Raz, and Avishay Tal
14:30	A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties (slides) Karl Bringmann, Nick Fischer, and Marvin Künnemann
15:00	Counting Basic-Irreducible Factors Mod p^k in deterministic poly-time and p-adic applications (slides) Ashish Dwivedi, Rajat Mittal, and Nitin Saxena
15:30	Break
16:00	Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity (slides) Lijie Chen and Ryan Williams
16:30	Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems Lijie Chen, Dylan McKay, Cody Murray, and Ryan Williams
17:00	Hardness Magnification Near State-of-the-Art Lower Bounds Igor Carboni Oliveira, Jan Pich, and Rahul Santhanam
17:30	Short Break
17:45	Rump Session

Saturday, July 20

8:30	Breakfast
9:00	Invited Talk On the NP-Hardness of 2-to-2 Games and Hypercontractivity (abstract, slides, video) Dor Minzer Khot's Unique Games Conjecture is a central open problem in the study of probabilistically checkable proofs (PCP's), which if true, would imply tight inapproximability results for wide class of optimization problems. A recent line of study has resolved the 2-to-2 Games Conjecture, a related but weaker variant of the Unique Games Conjecture. A central component in the proof of this conjecture is a characterization of sets whose edge-expansion bounded away from 1 in the Grassmann Graph, a problem closely related to hypercontractive-type inequalities. This talk will discuss this line of study. We will also discuss the relation to variants of the classical hypercontractive inequality on various domains.
10:00	Break
10:30	Sherali-Adams Strikes Back Ryan O'Donnell and Tselil Schramm
11:00	Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs Albert Atserias and Tuomas Hakoniemi
11:30	Resolution and the Binary Encoding of Combinatorial Principles (slides) Stefan Dantchev, Nicola Galesi, and Barnaby Martin
12:00	Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling (slides) Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere
12:30	Lunch
14:00	UG-hardness to NP-hardness by Losing Half (slides) Amey Bhangale and Subhash Khot
14:30	Imperfect Gaps in Gap-ETH and PCPs (slides) Mitali Bafna and Nikhil Vyas
15:00	Optimal Short-Circuit Resilient Formulas (slides) Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew
15:30	Break
16:00	From DNF Compression to Sunflower Theorems via Regularity (slides) Shachar Lovett, Noam Solomon, and Jiapeng Zhang
16:30	Criticality of Regular Formulas Benjamin Rossman
17:00	Parity Helps to Compute Majority (slides) Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan
17:30	End of the conference