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.

Wednesday, July 17

19:30–22:00Opening Reception

Thursday, July 18

8:30Breakfast
9:00 Limits on the Universal Method for Matrix Multiplication

Josh Alman

and

Barriers for Fast Matrix Multiplication from Irreversibility

Matthias Christandl, Péter Vrana, and Jeroen Zuiddam

10:00Break
10:30 Fourier and Circulant Matrices are Not Rigid

Allen Liu and Zeev Dvir

11:00 Typically-Correct Derandomization for Small Time and Space

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

Nader Bshouty

12:30Lunch
14:00 Average-Case Quantum Advantage with Shallow Circuits

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:30Break
16:00 Equality Alone Does not Simulate Randomness

Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals

16:30 Optimality of Linear Sketching under Modular Updates

Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev

17:00 Optimal Separation and Strong Direct Sum for Randomized Query Complexity

Joshua Brody and Eric Blais

17:30Short Break
17:45Business meeting

Friday, July 19

8:30Breakfast
9:00 Invited Talk
Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning

Ran Raz

10:00Break
10:30 Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

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

Eshan Chattopadhyay, Anindya De, and Rocco Servedio

12:30Lunch
14:00 Time-Space Lower Bounds for Two-Pass Learning

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

Karl Bringmann, Nick Fischer, and Marvin Künnemann

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

Ashish Dwivedi, Rajat Mittal, and Nitin Saxena

15:30Break
16:00 Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity

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

8:30Breakfast
9:00 Invited Talk
On the NP-Hardness of 2-to-2 Games and Hypercontractivity

Dor Minzer

10:00Break
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

Stefan Dantchev, Nicola Galesi, and Barnaby Martin

12:00 Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere

12:30Lunch
14:00 UG-hardness to NP-hardness by Losing Half

Amey Bhangale and Subhash Khot

14:30 Imperfect Gaps in Gap-ETH and PCPs

Mitali Bafna and Nikhil Vyas

15:00 Optimal Short-Circuit Resilient Formulas

Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew

15:30Break
16:00 From DNF Compression to Sunflower Theorems via Regularity

Shachar Lovett, Noam Solomon, and Jiapeng Zhang

16:30 Criticality of Regular Formulas

Benjamin Rossman

17:00 Parity Helps to Compute Majority

Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan

17:30End of the conference

Organized by:

In Cooperation with:

Sponsored by:

Microsoft Research