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 |