CCC 2019 July 17-20, 2019, New Brunswick, NJ, USA

34th Computational Complexity Conference (CCC 2019)



Amir Shpilka (Ed.)
ISBN 978-3-95977-116-0, LIPICS Vol. 137 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 18 MB)
Search Publication Server

Authors
  • Alman, Josh
  • Atserias, Albert
  • Bafna, Mitali
  • Bhangale, Amey
  • Blais, Eric
  • Braverman, Mark
  • Bringmann, Karl
  • Brody, Joshua
  • Bshouty, Nader H.
  • Chattopadhyay, Arkadev
  • Chattopadhyay, Eshan
  • Chen, Lijie
  • Christandl, Matthias
  • Coudron, Matthew
  • Dantchev, Stefan
  • De, Anindya
  • de Rezende, Susanna F.
  • Doron, Dean
  • Dvir, Zeev
  • Dwivedi, Ashish
  • Efremenko, Klim
  • Fischer, Nick
  • Galesi, Nicola
  • Garg, Sumegha
  • Gelles, Ran
  • Hakoniemi, Tuomas
  • Harrow, Aram W.
  • Hatami, Pooya
  • Hosseini, Kaave
  • Hoza, William M.
  • Khot, Subhash
  • Künnemann, Marvin
  • Lee, Chin Ho
  • Le Gall, François
  • Liu, Allen
  • Li, Xin
  • Lovett, Shachar
  • Martin, Barnaby
  • McKay, Dylan M.
  • Meir, Or
  • Mittal, Rajat
  • Murray, Cody D.
  • Nordström, Jakob
  • O'Donnell, Ryan
  • Oliveira, Igor Carboni
  • Pich, Ján
  • Raz, Ran
  • Robere, Robert
  • Rossman, Benjamin
  • Santhanam, Rahul
  • Saxena, Nitin
  • Schramm, Tselil
  • Servedio, Rocco A.
  • Shpilka, Amir
  • Slofstra, William
  • Solomon, Noam
  • Srinivasan, Srikanth
  • Stephens-Davidowitz, Noah
  • Tal, Avishay
  • Vinyals, Marc
  • Vrana, Péter
  • Vyas, Nikhil
  • Williams, R. Ryan
  • Yaroslavtsev, Grigory
  • Yitayew, Michael A.
  • Zhang, Jiapeng
  • Zuiddam, Jeroen
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Shpilka, Amir

    Abstract | Document (374 KB) | BibTeX

    Criticality of Regular Formulas
    Authors: Rossman, Benjamin

    Abstract | Document (693 KB) | BibTeX

    Almost Optimal Distribution-Free Junta Testing
    Authors: Bshouty, Nader H.

    Abstract | Document (494 KB) | BibTeX

    UG-Hardness to NP-Hardness by Losing Half
    Authors: Bhangale, Amey ; Khot, Subhash

    Abstract | Document (651 KB) | BibTeX

    Simple and Efficient Pseudorandom Generators from Gaussian Processes
    Authors: Chattopadhyay, Eshan ; De, Anindya ; Servedio, Rocco A.

    Abstract | Document (768 KB) | BibTeX

    From DNF Compression to Sunflower Theorems via Regularity
    Authors: Lovett, Shachar ; Solomon, Noam ; Zhang, Jiapeng

    Abstract | Document (435 KB) | BibTeX

    Resolution and the Binary Encoding of Combinatorial Principles
    Authors: Dantchev, Stefan ; Galesi, Nicola ; Martin, Barnaby

    Abstract | Document (686 KB) | BibTeX

    Fourier Bounds and Pseudorandom Generators for Product Tests
    Authors: Lee, Chin Ho

    Abstract | Document (613 KB) | BibTeX

    Sherali - Adams Strikes Back
    Authors: O'Donnell, Ryan ; Schramm, Tselil

    Abstract | Document (732 KB) | BibTeX

    Typically-Correct Derandomization for Small Time and Space
    Authors: Hoza, William M.

    Abstract | Document (755 KB) | BibTeX

    Optimal Short-Circuit Resilient Formulas
    Authors: Braverman, Mark ; Efremenko, Klim ; Gelles, Ran ; Yitayew, Michael A.

    Abstract | Document (628 KB) | BibTeX

    A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic
    Authors: Stephens-Davidowitz, Noah

    Abstract | Document (445 KB) | BibTeX

    Limits on the Universal Method for Matrix Multiplication
    Authors: Alman, Josh

    Abstract | Document (584 KB) | BibTeX

    Optimality of Linear Sketching Under Modular Updates
    Authors: Hosseini, Kaave ; Lovett, Shachar ; Yaroslavtsev, Grigory

    Abstract | Document (582 KB) | BibTeX

    Equality Alone Does not Simulate Randomness
    Authors: Chattopadhyay, Arkadev ; Lovett, Shachar ; Vinyals, Marc

    Abstract | Document (466 KB) | BibTeX

    Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications
    Authors: Dwivedi, Ashish ; Mittal, Rajat ; Saxena, Nitin

    Abstract | Document (678 KB) | BibTeX

    Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
    Authors: Doron, Dean ; Hatami, Pooya ; Hoza, William M.

    Abstract | Document (700 KB) | BibTeX

    Fourier and Circulant Matrices Are Not Rigid
    Authors: Dvir, Zeev ; Liu, Allen

    Abstract | Document (612 KB) | BibTeX

    Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
    Authors: de Rezende, Susanna F. ; Nordström, Jakob ; Meir, Or ; Robere, Robert

    Abstract | Document (511 KB) | BibTeX

    Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity
    Authors: Chen, Lijie ; Williams, R. Ryan

    Abstract | Document (859 KB) | BibTeX

    Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion
    Authors: Coudron, Matthew ; Harrow, Aram W.

    Abstract | Document (607 KB) | BibTeX

    Average-Case Quantum Advantage with Shallow Circuits
    Authors: Le Gall, François

    Abstract | Document (629 KB) | BibTeX

    Time-Space Lower Bounds for Two-Pass Learning
    Authors: Garg, Sumegha ; Raz, Ran ; Tal, Avishay

    Abstract | Document (721 KB) | BibTeX

    Parity Helps to Compute Majority
    Authors: Oliveira, Igor Carboni ; Santhanam, Rahul ; Srinivasan, Srikanth

    Abstract | Document (575 KB) | BibTeX

    Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs
    Authors: Atserias, Albert ; Hakoniemi, Tuomas

    Abstract | Document (522 KB) | BibTeX

    Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision
    Authors: Coudron, Matthew ; Slofstra, William

    Abstract | Document (537 KB) | BibTeX

    Barriers for Fast Matrix Multiplication from Irreversibility
    Authors: Christandl, Matthias ; Vrana, Péter ; Zuiddam, Jeroen

    Abstract | Document (527 KB) | BibTeX

    Hardness Magnification near State-Of-The-Art Lower Bounds
    Authors: Oliveira, Igor Carboni ; Pich, Ján ; Santhanam, Rahul

    Abstract | Document (778 KB) | BibTeX

    Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions
    Authors: Li, Xin

    Abstract | Document (781 KB) | BibTeX

    Optimal Separation and Strong Direct Sum for Randomized Query Complexity
    Authors: Blais, Eric ; Brody, Joshua

    Abstract | Document (540 KB) | BibTeX

    Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems
    Authors: Chen, Lijie ; McKay, Dylan M. ; Murray, Cody D. ; Williams, R. Ryan

    Abstract | Document (753 KB) | BibTeX

    A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties
    Authors: Bringmann, Karl ; Fischer, Nick ; Künnemann, Marvin

    Abstract | Document (694 KB) | BibTeX

    Imperfect Gaps in Gap-ETH and PCPs
    Authors: Bafna, Mitali ; Vyas, Nikhil

    Abstract | Document (533 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI