default search action
34th CCC 2019: New Brunswick, NJ, USA
- Amir Shpilka:
34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA. LIPIcs 137, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019, ISBN 978-3-95977-116-0 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:14
- Benjamin Rossman:
Criticality of Regular Formulas. 1:1-1:28 - Nader H. Bshouty:
Almost Optimal Distribution-Free Junta Testing. 2:1-2:13 - Amey Bhangale, Subhash Khot:
UG-Hardness to NP-Hardness by Losing Half. 3:1-3:20 - Eshan Chattopadhyay, Anindya De, Rocco A. Servedio
:
Simple and Efficient Pseudorandom Generators from Gaussian Processes. 4:1-4:33 - Shachar Lovett, Noam Solomon, Jiapeng Zhang:
From DNF Compression to Sunflower Theorems via Regularity. 5:1-5:14 - Stefan S. Dantchev
Resolution and the Binary Encoding of Combinatorial Principles. 6:1-6:25 - Chin Ho Lee:
Fourier Bounds and Pseudorandom Generators for Product Tests. 7:1-7:25 - Ryan O'Donnell, Tselil Schramm
Sherali - Adams Strikes Back. 8:1-8:30 - William M. Hoza
Typically-Correct Derandomization for Small Time and Space. 9:1-9:39 - Mark Braverman, Klim Efremenko
Optimal Short-Circuit Resilient Formulas. 10:1-10:22 - Noah Stephens-Davidowitz:
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic. 11:1-11:8 - Josh Alman:
Limits on the Universal Method for Matrix Multiplication. 12:1-12:24 - Kaave Hosseini
Optimality of Linear Sketching Under Modular Updates. 13:1-13:17 - Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Equality Alone Does not Simulate Randomness. 14:1-14:11 - Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications. 15:1-15:29 - Dean Doron
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. 16:1-16:34 - Zeev Dvir, Allen Liu:
Fourier and Circulant Matrices Are Not Rigid. 17:1-17:23 - Susanna F. de Rezende
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. 18:1-18:16 - Lijie Chen, R. Ryan Williams
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. 19:1-19:43 - Matthew Coudron
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. 20:1-20:25 - François Le Gall:
Average-Case Quantum Advantage with Shallow Circuits. 21:1-21:20 - Sumegha Garg, Ran Raz
Time-Space Lower Bounds for Two-Pass Learning. 22:1-22:39 - Igor Carboni Oliveira, Rahul Santhanam
Parity Helps to Compute Majority. 23:1-23:17 - Albert Atserias
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. 24:1-24:20 - Matthew Coudron
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. 25:1-25:20 - Matthias Christandl
Barriers for Fast Matrix Multiplication from Irreversibility. 26:1-26:17 - Igor Carboni Oliveira, Ján Pich
Hardness Magnification near State-Of-The-Art Lower Bounds. 27:1-27:29 - Xin Li:
Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. 28:1-28:49 - Eric Blais, Joshua Brody:
Optimal Separation and Strong Direct Sum for Randomized Query Complexity. 29:1-29:17 - Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. 30:1-30:21 - Karl Bringmann, Nick Fischer, Marvin Künnemann:
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. 31:1-31:27 - Mitali Bafna, Nikhil Vyas:
Imperfect Gaps in Gap-ETH and PCPs. 32:1-32:19
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-22 19:32 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: