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
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
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
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
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
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
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
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
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
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
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
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
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
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
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
by Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
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
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
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
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
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
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
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
On Multiparty Communication with Large versus Unbounded Error
by Alexander A. Sherstov