Computational Complexity Conference

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 pk 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 Existsk-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

Organized by:

In Cooperation with:

Sponsored by:

Microsoft Research