CCC 2017 July 6-9, 2017 - Riga, Latvia

32nd Computational Complexity Conference (CCC 2017)



Ryan O'Donnell (Ed.)
ISBN 978-3-95977-040-8, LIPICS Vol. 79 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 20 MB)
Search Publication Server

Authors
  • Aaronson, Scott
  • Anshu, Anurag
  • Arunachalam, Srinivasan
  • Belovs, Aleksandrs
  • Ben-David, Shalev
  • Blaeser, Markus
  • Blais, Eric
  • Bringmann, Karl
  • Canonne, Clément L.
  • Chen, Lijie
  • Chen, Xi
  • Dagan, Yuval
  • De, Anindya
  • de Oliveira Oliveira, Mateus
  • de Wolf, Ronald
  • Dinur, Irit
  • Filmus, Yuval
  • Garg, Ankit
  • Ghosh, Mrinalkanti
  • Göös, Mika
  • Gur, Tom
  • Haramaty, Elad
  • Hatami, Hamed
  • Hirahara, Shuichi
  • Ikenmeyer, Christian
  • Ivanyos, Gábor
  • Jain, Rahul
  • Jindal, Gorav
  • Kamath, Pritish
  • Kayal, Neeraj
  • Kothari, Robin
  • Kumar, Mrinal
  • Lauria, Massimo
  • Lee, Chin Ho
  • Lee, Troy
  • Livni Navon, Inbal
  • Li, Yaqiao
  • Milovanov, Alexey
  • Minahan, Daniel
  • Mossel, Elchanan
  • Murray, Cody D.
  • Nair, Vineet
  • Nayak, Ashwin
  • Neeman, Joe
  • Nguyen, Danny
  • Nordström, Jakob
  • O'Donnell, Ryan
  • Oliveira, Igor C. Carboni
  • Pak, Igor
  • Pandey, Anurag
  • Pitassi, Toniann
  • Potechin, Aaron
  • Prakriya, Gautam
  • Pudlák, Pavel
  • Qiao, Youming
  • Saha, Chandan
  • Santha, Miklos
  • Santhanam, Rahul
  • Saptharishi, Ramprasad
  • Scheder, Dominik
  • Servedio, Rocco A.
  • Steinberger, John P.
  • Tal, Avishay
  • Tan, Li-Yang
  • Tavenas, Sébastien
  • Tell, Roei
  • Thapen, Neil
  • Touchette, Dave
  • Tulsiani, Madhur
  • van Melkebeek, Dieter
  • Vereshchagin, Nikolay
  • Viola, Emanuele
  • Volkovich, Ilya
  • Waingarten, Erik
  • Watson, Thomas
  • Williams, R. Ryan
  • Xie, Jinyu
  • Yang, Siyi
  • Zuiddam, Jeroen
    		•

    		  
    Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers
    Authors: O'Donnell, Ryan

    Abstract | Document (406 KB) | BibTeX

    Random Resolution Refutations
    Authors: Pudlák, Pavel ; Thapen, Neil

    Abstract | Document (525 KB) | BibTeX

    Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
    Authors: Lauria, Massimo ; Nordström, Jakob

    Abstract | Document (607 KB) | BibTeX

    Representations of Monotone Boolean Functions by Linear Programs
    Authors: de Oliveira Oliveira, Mateus ; Pudlák, Pavel

    Abstract | Document (522 KB) | BibTeX

    A Note on Amortized Branching Program Complexity
    Authors: Potechin, Aaron

    Abstract | Document (506 KB) | BibTeX

    Derandomizing Isolation in Space-Bounded Settings
    Authors: van Melkebeek, Dieter ; Prakriya, Gautam

    Abstract | Document (764 KB) | BibTeX

    The Computational Complexity of Integer Programming with Alternations
    Authors: Nguyen, Danny ; Pak, Igor

    Abstract | Document (583 KB) | BibTeX

    On the Average-Case Complexity of MCSP and Its Variants
    Authors: Hirahara, Shuichi ; Santhanam, Rahul

    Abstract | Document (591 KB) | BibTeX

    Easiness Amplification and Uniform Circuit Lower Bounds
    Authors: Murray, Cody D. ; Williams, R. Ryan

    Abstract | Document (593 KB) | BibTeX

    PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster
    Authors: Scheder, Dominik ; Steinberger, John P.

    Abstract | Document (561 KB) | BibTeX

    Noise Stability Is Computable and Approximately Low-Dimensional
    Authors: De, Anindya ; Mossel, Elchanan ; Neeman, Joe

    Abstract | Document (562 KB) | BibTeX

    From Weak to Strong LP Gaps for All CSPs
    Authors: Ghosh, Mrinalkanti ; Tulsiani, Madhur

    Abstract | Document (690 KB) | BibTeX

    Query-to-Communication Lifting for P^NP
    Authors: Göös, Mika ; Kamath, Pritish ; Pitassi, Toniann ; Watson, Thomas

    Abstract | Document (739 KB) | BibTeX

    Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
    Authors: Tell, Roei

    Abstract | Document (980 KB) | BibTeX

    Bounded Independence Plus Noise Fools Products
    Authors: Haramaty, Elad ; Lee, Chin Ho ; Viola, Emanuele

    Abstract | Document (598 KB) | BibTeX

    Tight Bounds on the Fourier Spectrum of AC0
    Authors: Tal, Avishay

    Abstract | Document (742 KB) | BibTeX

    Trading Information Complexity for Error
    Authors: Dagan, Yuval ; Filmus, Yuval ; Hatami, Hamed ; Li, Yaqiao

    Abstract | Document (854 KB) | BibTeX

    Stochasticity in Algorithmic Statistics for Polynomial Time
    Authors: Milovanov, Alexey ; Vereshchagin, Nikolay

    Abstract | Document (545 KB) | BibTeX

    Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness
    Authors: Oliveira, Igor C. Carboni ; Santhanam, Rahul

    Abstract | Document (929 KB) | BibTeX

    A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs
    Authors: Kumar, Mrinal

    Abstract | Document (504 KB) | BibTeX

    On Algebraic Branching Programs of Small Width
    Authors: Bringmann, Karl ; Ikenmeyer, Christian ; Zuiddam, Jeroen

    Abstract | Document (689 KB) | BibTeX

    Reconstruction of Full Rank Algebraic Branching Programs
    Authors: Kayal, Neeraj ; Nair, Vineet ; Saha, Chandan ; Tavenas, Sébastien

    Abstract | Document (1,012 KB) | BibTeX

    Complexity-Theoretic Foundations of Quantum Supremacy Experiments
    Authors: Aaronson, Scott ; Chen, Lijie

    Abstract | Document (1,028 KB) | BibTeX

    Augmented Index and Quantum Streaming Algorithms for DYCK(2)
    Authors: Nayak, Ashwin ; Touchette, Dave

    Abstract | Document (685 KB) | BibTeX

    Separating Quantum Communication and Approximate Rank
    Authors: Anshu, Anurag ; Ben-David, Shalev ; Garg, Ankit ; Jain, Rahul ; Kothari, Robin ; Lee, Troy

    Abstract | Document (723 KB) | BibTeX

    Optimal Quantum Sample Complexity of Learning Algorithms
    Authors: Arunachalam, Srinivasan ; de Wolf, Ronald

    Abstract | Document (669 KB) | BibTeX

    Settling the Query Complexity of Non-Adaptive Junta Testing
    Authors: Chen, Xi ; Servedio, Rocco A. ; Tan, Li-Yang ; Waingarten, Erik ; Xie, Jinyu

    Abstract | Document (714 KB) | BibTeX

    An Adaptivity Hierarchy Theorem for Property Testing
    Authors: Canonne, Clément L. ; Gur, Tom

    Abstract | Document (675 KB) | BibTeX

    Distribution Testing Lower Bounds via Reductions from Communication Complexity
    Authors: Blais, Eric ; Canonne, Clément L. ; Gur, Tom

    Abstract | Document (1,090 KB) | BibTeX

    Exponentially Small Soundness for the Direct Product Z-Test
    Authors: Dinur, Irit ; Livni Navon, Inbal

    Abstract | Document (781 KB) | BibTeX

    On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
    Authors: Belovs, Aleksandrs ; Ivanyos, Gábor ; Qiao, Youming ; Santha, Miklos ; Yang, Siyi

    Abstract | Document (641 KB) | BibTeX

    An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields
    Authors: Kumar, Mrinal ; Saptharishi, Ramprasad

    Abstract | Document (725 KB) | BibTeX

    Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas
    Authors: Minahan, Daniel ; Volkovich, Ilya

    Abstract | Document (489 KB) | BibTeX

    Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces
    Authors: Blaeser, Markus ; Jindal, Gorav ; Pandey, Anurag

    Abstract | Document (520 KB) | BibTeX

    		  



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