CCC'19 - Accepted Papers

• Criticality of Regular Formulas
  Benjamin Rossman
• Almost Optimal Distribution-free Junta Testing
  Nader Bshouty
• UG-hardness to NP-hardness by Losing Half
  Amey Bhangale and Subhash Khot
• Simple and efficient pseudorandom generators from Gaussian processes
  Eshan Chattopadhyay, Anindya De, and Rocco Servedio
• From DNF compression to sunflower theorems via regularity
  Shachar Lovett, Noam Solomon, and Jiapeng Zhang
• Resolution and the binary encoding of combinatorial principles
  Stefan Dantchev, Nicola Galesi, and Barnaby Martin
• Fourier bounds and pseudorandom generators for product tests
  Chin Ho Lee
• Sherali-Adams Strikes Back
  Ryan O'Donnell and Tselil Schramm
• Typically-Correct Derandomization for Small Time and Space
  William Hoza
• Optimal Short-Circuit Resilient Formulas
  Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew
• A time-distance trade-off for GDD with preprocessing---Instantiating the DLW heuristic
  Noah Stephens-Davidowitz
• Limits on the Universal Method for Matrix Multiplication
  Josh Alman
• Optimality of Linear Sketching under Modular Updates
  Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev
• Equality Alone Does not Simulate Randomness
  Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals
• Counting basic-irreducible factors mod p^k in deterministic poly-time and p-adic applications
  Ashish Dwivedi, Rajat Mittal, and Nitin Saxena
• Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
  Dean Doron, Pooya Hatami, and William Hoza
• Fourier and Circulant Matrices are Not Rigid
  Allen Liu and Zeev Dvir
• Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
  Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere
• Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity
  Lijie Chen and Ryan Williams
• Universality of EPR pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion
  Matthew Coudron and Aram Harrow
• Average-Case Quantum Advantage with Shallow Circuits
  Francois Le Gall
• Time-Space Lower Bounds for Two-Pass Learning
  Sumegha Garg, Ran Raz, and Avishay Tal
• Parity Helps to Compute Majority
  Igor Oliveira, Rahul Santhanam, and Srikanth Srinivasan
• Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs
  Albert Atserias and Tuomas Hakoniemi
• Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
  Matthew Coudron and William Slofstra
• Barriers for fast matrix multiplication from irreversibility
  Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
• Hardness magnification near state-of-the-art lower bounds
  Igor Carboni Oliveira, Jan Pich, and Rahul Santhanam
• Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions
  Xin Li
• Optimal Separation and Strong Direct Sum for Randomized Query Complexity
  Joshua Brody and Eric Blais
• Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems
  Lijie Chen, Dylan McKay, Cody Murray, and Ryan Williams
• A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties
  Karl Bringmann, Nick Fischer, and Marvin Künnemann
• Imperfect Gaps in Gap-ETH and PCPs
  Mitali Bafna and Nikhil Vyas