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