Computational Complexity Conference

CCC'16 - Accepted Papers

(In order of submission)

  • Decoding Reed-Muller codes over product sets
    John Kim and Swastik Kopparty
  • Non-Malleable Extractors - New Tools and Improved Constructions
    Gil Cohen
  • Invariance principle on the slice
    Yuval Filmus, Guy Kindler, Elchanan Mossel and Karl Wimmer
  • New Non-uniform Lower Bounds for Uniform Classes
    Lance Fortnow and Rahul Santhanam
  • A linear time algorithm for quantum 2-SAT
    Niel de Beaudrap and Sevag Gharibian
  • Complexity classification of two-qubit commuting hamiltonians
    Adam Bouland, Laura Mancinska and Xue Zhang
  • A Composition Theorem for Conical Juntas
    Mika Goos and T.S. Jayram
  • Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
    Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka and Ben Lee Volk
  • Limits of Minimum Circuit Size Problem as Oracle
    Shuichi Hirahara and Osamu Watanabe
  • New hardness results for graph and hypergraph colorings
    Joshua Brakensiek and Venkatesan Guruswami
  • Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
    Ryan Williams
  • Arithmetic circuits with locally low algebraic rank
    Mrinal Kumar and Shubhangi Saraf
  • Sums of products of polynomials in few variables : lower bounds and polynomial identity testing
    Mrinal Kumar and Shubhangi Saraf
  • Lower bounds for constant query affine-invariant LCCs and LTCs
    Arnab Bhattacharyya and Sivakanth Gopi
  • New Extractors for Interleaved Sources
    Eshan Chattopadhyay and David Zuckerman
  • Understanding PPA-Completeness
    Xiaotie Deng, Jack Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi and Zeying Xu
  • Harmonicity and Invariance on Slices of the Boolean Cube
    Yuval Filmus and Elchanan Mossel
  • Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
    Irit Dinur and Or Meir
  • Tight bounds for communication assisted agreement distillation
    Venkatesan Guruswami and Jaikumar Radhakrishnan
  • Nearly optimal separations between communication (or query) complexity and partitions
    Andris Ambainis, Mārtiņš Kokainis and Robin Kothari
  • Identity Testing for constant-width, and commutative, read-once oblivious ABPs
    Rohit Gurjar, Arpita Korwar and Nitin Saxena
  • Proof Complexity Lower Bounds from Algebraic Circuit Complexity
    Michael A. Forbes, Amir Shpilka, Iddo Tzameret and Avi Wigderson
  • Learning Algorithms from Natural Proofs
    Marco Carmosino, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova
  • On the sum-of-squares degree of symmetric quadratic functions
    Troy Lee, Anupam Prakash, Ronald de Wolf and Henry Yuen
  • Pseudorandomness when the odds are against you
    Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets and Ronen Shaltiel
  • Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
    Michael A. Forbes, Mrinal Kumar and Ramprasad Saptharishi
  • Polynomial bounds for decoupling, with applications
    Ryan O'Donnell and Yu Zhao
  • Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
    Ruiwen Chen, Rahul Santhanam and Srikanth Srinivasan
  • Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
    Scott Aaronson, Andris Ambainis, Jānis Iraids, Mārtiņš Kokainis and Juris Smotrovs
  • Sculpting Quantum Speedups
    Scott Aaronson and Shalev Ben-David
  • Tight SoS-degree bounds for approximate Nash equilibria
    Aram Harrow, Anand Natarajan and Xiaodi Wu
  • Degree and Sensitivity: tails of two distributions
    Parikshit Gopalan, Rocco Servedio and Avi Wigderson
  • New Characterizations in Turnstile Streams with Applications
    Yuqing Ai, Wei Hu, Yi Li and David P. Woodruff
  • Reconstruction of Real depth-3 Circuits with top fan-in 2
    Gaurav Sinha

Organized by:

Computational Complexity Foundation Inc.

Exploring the Limits of Computation (ELC), KAKENHI Japan

In Cooperation with:


Sponsored by:

Microsoft Research