| 2019 | 34th Computational Complexity Conference, CCC 2019, New Brunswick, NJ, USA, July 18-20, 2019 Amir Shpilka |
| 2019 | A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. Karl Bringmann, Nick Fischer, Marvin Künnemann |
| 2019 | A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic. Noah Stephens-Davidowitz |
| 2019 | Almost Optimal Distribution-Free Junta Testing. Nader H. Bshouty |
| 2019 | Average-Case Quantum Advantage with Shallow Circuits. François Le Gall |
| 2019 | Barriers for Fast Matrix Multiplication from Irreversibility. Matthias Christandl, Péter Vrana, Jeroen Zuiddam |
| 2019 | Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. Matthew Coudron, William Slofstra |
| 2019 | Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications. Ashish Dwivedi, Rajat Mittal, Nitin Saxena |
| 2019 | Criticality of Regular Formulas. Benjamin Rossman |
| 2019 | Equality Alone Does not Simulate Randomness. Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals |
| 2019 | Fourier Bounds and Pseudorandom Generators for Product Tests. Chin Ho Lee |
| 2019 | Fourier and Circulant Matrices Are Not Rigid. Zeev Dvir, Allen Liu |
| 2019 | From DNF Compression to Sunflower Theorems via Regularity. Shachar Lovett, Noam Solomon, Jiapeng Zhang |
| 2019 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2019 | Hardness Magnification near State-Of-The-Art Lower Bounds. Igor Carboni Oliveira, Ján Pich, Rahul Santhanam |
| 2019 | Imperfect Gaps in Gap-ETH and PCPs. Mitali Bafna, Nikhil Vyas |
| 2019 | Limits on the Universal Method for Matrix Multiplication. Josh Alman |
| 2019 | Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. Dean Doron, Pooya Hatami, William M. Hoza |
| 2019 | Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. Xin Li |
| 2019 | Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Susanna F. de Rezende, Jakob Nordström, Or Meir, Robert Robere |
| 2019 | Optimal Separation and Strong Direct Sum for Randomized Query Complexity. Eric Blais, Joshua Brody |
| 2019 | Optimal Short-Circuit Resilient Formulas. Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew |
| 2019 | Optimality of Linear Sketching Under Modular Updates. Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev |
| 2019 | Parity Helps to Compute Majority. Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan |
| 2019 | Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams |
| 2019 | Resolution and the Binary Encoding of Combinatorial Principles. Stefan S. Dantchev, Nicola Galesi, Barnaby Martin |
| 2019 | Sherali - Adams Strikes Back. Ryan O'Donnell, Tselil Schramm |
| 2019 | Simple and Efficient Pseudorandom Generators from Gaussian Processes. Eshan Chattopadhyay, Anindya De, Rocco A. Servedio |
| 2019 | Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. Albert Atserias, Tuomas Hakoniemi |
| 2019 | Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. Lijie Chen, R. Ryan Williams |
| 2019 | Time-Space Lower Bounds for Two-Pass Learning. Sumegha Garg, Ran Raz, Avishay Tal |
| 2019 | Typically-Correct Derandomization for Small Time and Space. William M. Hoza |
| 2019 | UG-Hardness to NP-Hardness by Losing Half. Amey Bhangale, Subhash Khot |
| 2019 | Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. Matthew Coudron, Aram W. Harrow |