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.
Videos:
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
Friday, July 19
8:30  Breakfast 
9:00 
Invited Talk
Learning Fast Requires Good Memory: TimeSpace 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 superlinear size or a superpolynomial 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 
NearOptimal Pseudorandom Generators for ConstantDepth ReadOnce Formulas
(slides)
Dean Doron, Pooya Hatami, and William Hoza

11:00 
NonMalleable Extractors and NonMalleable 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 
TimeSpace Lower Bounds for TwoPass Learning
(slides)
Sumegha Garg, Ran Raz, and Avishay Tal

14:30 
A FineGrained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^{k}ForallQuantified FirstOrder Graph Properties
(slides)
Karl Bringmann, Nick Fischer, and Marvin Künnemann

15:00 
Counting BasicIrreducible Factors Mod p^{k} in deterministic polytime and padic 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 KarpLipton Theorems
Lijie Chen, Dylan McKay, Cody Murray, and Ryan Williams

17:00 
Hardness Magnification Near StateoftheArt 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 NPHardness of 2to2 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 2to2 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 edgeexpansion bounded away from 1 in the Grassmann Graph, a problem closely related to hypercontractivetype 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 
SheraliAdams Strikes Back
Ryan O'Donnell and Tselil Schramm

11:00 
SizeDegree TradeOffs for SumsofSquares 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 SizeDegree Tradeoffs from Reversible Pebbling
(slides)
Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere

12:30  Lunch 
14:00 
UGhardness to NPhardness by Losing Half
(slides)
Amey Bhangale and Subhash Khot

14:30 
Imperfect Gaps in GapETH and PCPs
(slides)
Mitali Bafna and Nikhil Vyas

15:00 
Optimal ShortCircuit 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 