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:00Opening Reception

Thursday, July 18

9:00 Limits on the Universal Method for Matrix Multiplication

Josh Alman


Barriers for Fast Matrix Multiplication from Irreversibility (slides)

Matthias Christandl, Péter Vrana, and Jeroen Zuiddam

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

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

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:30Short Break
17:45Business meeting

Friday, July 19

9:00 Invited Talk
Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning (abstract, slides, video)

Ran Raz

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

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 Existsk-Forall-Quantified First-Order Graph Properties (slides)

Karl Bringmann, Nick Fischer, and Marvin Künnemann

15:00 Counting Basic-Irreducible Factors Mod pk in deterministic poly-time and p-adic applications (slides)

Ashish Dwivedi, Rajat Mittal, and Nitin Saxena

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:30Short Break
17:45Rump Session

Saturday, July 20

9:00 Invited Talk
On the NP-Hardness of 2-to-2 Games and Hypercontractivity (abstract, slides, video)

Dor Minzer

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

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

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:30End of the conference

Organized by:

In Cooperation with:

Sponsored by:

Microsoft Research