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