Volume 14 (2018)
Vol 14, Article 1 (pp 1-27)
Linear-Time Algorithm for Quantum 2SAT
by Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang
Vol 14, Article 2 (pp 1-2) [CCC17 Spec Issue]
Special Issue: CCC 2017: Guest Editor's Foreword
by Shachar Lovett and Ryan O'Donnell
Vol 14, Article 3 (pp 1-21) [CCC17 Spec Issue]
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
Vol 14, Article 4 (pp 1-29)
Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels
by Benny Applebaum, Liron David, and Guy Even
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
Vol 14, Article 6 (pp 1-73) [CCC17 Spec Issue]
Trading Information Complexity for Error
by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li
Vol 14, Article 7 (pp 1-45)
Quantum Homomorphic Encryption for Polynomial-Size Circuits
by Yfke Dulek, Christian Schaffner, and Florian Speelman
Vol 14, Article 8 (pp 1-35)
The Complexity of Computing the Optimal Composition of Differential Privacy
by Jack Murtagh and Salil Vadhan
Vol 14, Article 9 (pp 1-55) [CCC16 Spec Issue]
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan
Vol 14, Article 10 (pp 1-33) [CCC17 Spec Issue]
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
Vol 14, Article 11 (pp 1-37)
How to Verify a Quantum Computation
by Anne Broadbent
Vol 14, Article 12 (pp 1-24)
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
by Swastik Kopparty and Srikanth Srinivasan
Vol 14, Article 13 (pp 1-17)
On the Hardness of Learning With Errors with Binary Secrets
by Daniele Micciancio
Vol 14, Article 14 (pp 1-29)
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
by Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
Vol 14, Article 15 (pp 1-24)
Quantum-Walk Speedup of Backtracking Algorithms
by Ashley Montanaro
Vol 14, Article 16 (pp 1-46)
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
by Neeraj Kayal, Chandan Saha, and Sébastien Tavenas
Vol 14, Article 17 (pp 1-25)
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates
by R. Ryan Williams
Vol 14, Article 18 (pp 1-45)
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits
by Michael A. Forbes, Amir Shpilka, and Ben Lee Volk
Vol 14, Article 19 (pp 1-46)
A Chasm Between Identity and Equivalence Testing with Conditional Queries
by Jayadev Acharya, Clément L. Canonne, and Gautam Kamath
Vol 14, Article 20 (pp 1-29)
Simplified Separation of Information and Communication
by Anup Rao and Makrand Sinha
Vol 14, Article 21 (pp 1-23)
Separation of Unbounded-Error Models in Multi-Party Communication Complexity
by Arkadev Chattopadhyay and Nikhil S. Mande
Vol 14, Article 22 (pp 1-17)
On Multiparty Communication with Large versus Unbounded Error
by Alexander A. Sherstov
List of Editors