default search action
Theory of Computing, Volume 14
Volume 14, Number 1, 2018
- Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang:
Linear-Time Algorithm for Quantum 2SAT. 1-27 - Shachar Lovett, Ryan O'Donnell:
Special Issue: CCC 2017: Guest Editor's Foreword. 1-2 - Markus Bläser, Gorav Jindal
, Anurag Pandey:
A Deterministic PTAS for the Commutative Rank of Matrix Spaces. 1-21 - Benny Applebaum, Liron David, Guy Even:
Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels. 1-29 - Shalev Ben-David, Robin Kothari
Randomized Query Complexity of Sabotaged and Composed Functions. 1-27 - Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li:
Trading Information Complexity for Error. 1-73 - Yfke Dulek, Christian Schaffner
Quantum Homomorphic Encryption for Polynomial-Size Circuits. 1-45 - Jack Murtagh, Salil P. Vadhan:
The Complexity of Computing the Optimal Composition of Differential Privacy. 1-35 - Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. 1-55 - Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems. 1-33 - Anne Broadbent:
How to Verify a Quantum Computation. 1-37 - Swastik Kopparty, Srikanth Srinivasan
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression. 1-24 - Daniele Micciancio
On the Hardness of Learning With Errors with Binary Secrets. 1-17 - Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson:
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits. 1-29 - Ashley Montanaro
Quantum-Walk Speedup of Backtracking Algorithms. 1-24 - Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree. 1-46 - R. Ryan Williams
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates. 1-25 - Michael A. Forbes, Amir Shpilka
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. 1-45 - Jayadev Acharya, Clément L. Canonne
A Chasm Between Identity and Equivalence Testing with Conditional Queries. 1-46 - Anup Rao, Makrand Sinha:
Simplified Separation of Information and Communication. 1-29 - Arkadev Chattopadhyay, Nikhil S. Mande
Separation of Unbounded-Error Models in Multi-Party Communication Complexity. 1-23 - Alexander A. Sherstov:
On Multiparty Communication with Large versus Unbounded Error. 1-17
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-02-05 20:20 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: