Computational Complexity Conference

CCC'17 - Accepted Papers

  • Random resolution refutations
    Neil Thapen and Pavel Pudlak
  • Query-to-Communication Lifting for P^NP
    Mika Göös, Pritish Kamath, Toniann Pitassi and Thomas Watson
  • Trading information complexity for error
    Yuval Dagan, Yuval Filmus, Hamed Hatami and Yaqiao Li
  • From Weak to Strong LP Gaps for all CSPs
    Mrinalkanti Ghosh and Madhur Tulsiani
  • Tight bounds on The Fourier Spectrum of AC0
    Avishay Tal
  • On algebraic branching programs of small width
    Karl Bringmann, Christian Ikenmeyer and Jeroen Zuiddam
  • Bounded independence plus noise fools products
    Elad Haramaty, Chin Ho Lee and Emanuele Viola
  • A Note on Amortized Branching Program Complexity
    Aaron Potechin
  • Derandomizing Isolation in Space-Bounded Settings
    Dieter van Melkebeek and Gautam Prakriya
  • An Adaptivity Hierarchy Theorem for Property Testing
    Clément Canonne and Tom Gur
  • Separating Quantum Communication and Approximate Rank
    Shalev Ben-David, Robin Kothari, Anurag Anshu, Ankit Garg, Rahul Jain and Troy Lee
  • Easiness Amplification and Uniform Circuit Lower Bounds
    Cody Murray and Ryan Williams
  • On the Average-Case Complexity of MCSP and its Variants
    Shuichi Hirahara and Rahul Santhanam
  • Reconstruction of full rank Algebraic Branching Programs
    Neeraj Kayal, Vineet Nair, Chandan Saha and Sebastien Tavenas
  • Optimal Quantum Sample Complexity of Learning Algorithms
    Srinivasan Arunachalam and Ronald de Wolf
  • Settling the query complexity of non-adaptive junta testing
    Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten and Jinyu Xie
  • Stochasticity in Algorithmic Statistics for Polynomial Time
    Alexey Milovanov and Nikolay Vereshchagin
  • Exponentially Small Soundness for the Direct Product Z-test
    Inbal Livni Navon and Irit Dinur
  • Augmented Index and Quantum Streaming Algorithms for DYCK(2)
    Ashwin Nayak and Dave Touchette
  • Noise Stability is Computable and approximately Low-Dimensional
    Anindya De, Elchanan Mossel and Joe Neeman
  • Representations of Monotone Boolean Functions by Linear Programs
    Mateus De Oliveira Oliveira and Pavel Pudlák
  • Complexity-Theoretic Foundations of Quantum Supremacy Experiments
    Scott Aaronson and Lijie Chen
  • A quadratic lower bound for homogeneous algebraic branching programs
    Mrinal Kumar
  • The computational complexity of integer programming with alternations
    Danny Nguyen and Igor Pak
  • PPSZ for General k-SAT — Making Hertli's Analysis Simpler and 3-SAT Faster
    Dominik Scheder and John Steinberger
  • Distribution Testing Lower Bounds via Reductions from Communication Complexity
    Eric Blais, Clément Canonne and Tom Gur
  • An exponential lower bound for homogeneous depth-5 circuits over finite fields
    Mrinal Kumar and Ramprasad Saptharishi
  • Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces
    Markus Blaeser, Gorav Jindal and Anurag Pandey
  • On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz
    Aleksandrs Belovs, Gabor Ivanyos, Youming Qiao, Miklos Santha and Siyi Yang
  • Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
    Igor Carboni Oliveira and Rahul Santhanam
  • Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas
    Daniel Minahan and Ilya Volkovich
  • Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
    Roei Tell
  • Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
    Massimo Lauria and Jakob Nordstrom

Organized by:

Computational Complexity Foundation Inc.

In Cooperation with:

EATCS

Sponsored by:

Microsoft Research

University of Latvia