- Shachar Lovett, Ryan O'Donnell:
Special Issue: CCC 2017: Guest Editor's Foreword. Theory Comput. 14(1): 1-2 (2018) - Daniele Micciancio
:
On the Hardness of Learning With Errors with Binary Secrets. Theory Comput. 14(1): 1-17 (2018) - Ashley Montanaro
:
Quantum-Walk Speedup of Backtracking Algorithms. Theory Comput. 14(1): 1-24 (2018) - Jack Murtagh, Salil P. Vadhan:
The Complexity of Computing the Optimal Composition of Differential Privacy. Theory Comput. 14(1): 1-35 (2018) - Anup Rao, Makrand Sinha:
Simplified Separation of Information and Communication. Theory Comput. 14(1): 1-29 (2018) - Alexander A. Sherstov:
On Multiparty Communication with Large versus Unbounded Error. Theory Comput. 14(1): 1-17 (2018) - R. Ryan Williams
:
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates. Theory Comput. 14(1): 1-25 (2018) - 2017
- Mrinal Kumar, Shubhangi Saraf:
Arithmetic Circuits with Locally Low Algebraic Rank. Theory Comput. 13(1): 1-33 (2017) - Maria-Florina Balcan, Mark Braverman:
Nash Equilibria in Perturbation-Stable Games. Theory Comput. 13(1): 1-31 (2017) - Jop Briët, Oded Regev, Rishi Saket:
Tight Hardness of the Non-Commutative Grothendieck Problem. Theory Comput. 13(1): 1-24 (2017) - Amin Coja-Oghlan, Oliver Cooley
, Mihyun Kang
, Kathrin Skubch:
The Minimum Bisection in the Planted Bisection Model. Theory Comput. 13(1): 1-22 (2017) - Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Theory Comput. 13(1): 1-36 (2017) - David Felber, Rafail Ostrovsky:
A Randomized Online Quantile Summary in O((1/ε) log(1/ε)) Words. Theory Comput. 13(1): 1-17 (2017) - Hervé Fournier, Nutan Limaye, Meena Mahajan
, Srikanth Srinivasan
:
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. Theory Comput. 13(1): 1-34 (2017) - Justin Gilmer, Michal Koucký
, Michael E. Saks:
A Communication Game Related to the Sensitivity Conjecture. Theory Comput. 13(1): 1-18 (2017) - Joshua A. Grochow:
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds. Theory Comput. 13(1): 1-15 (2017) - Rohit Gurjar, Arpita Korwar, Nitin Saxena
:
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs. Theory Comput. 13(1): 1-21 (2017) - Venkatesan Guruswami, Euiwoong Lee:
Towards a Characterization of Approximation Resistance for Symmetric CSPs. Theory Comput. 13(1): 1-24 (2017) - David G. Harris, Aravind Srinivasan:
A Constructive Lovász Local Lemma for Permutations. Theory Comput. 13(1): 1-41 (2017) - Prahladh Harsha
:
Special Issue: CCC 2016: Guest Editor's Foreword. Theory Comput. 13(1): 1-3 (2017) - Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright:
Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. 13(1): 1-51 (2017) - Johan Håstad, Rajsekar Manokaran:
On the Hardness of Approximating Balanced Homogenous 3-Lin. Theory Comput. 13(1): 1-19 (2017) - John Y. Kim, Swastik Kopparty:
Decoding Reed-Muller Codes over Product Sets. Theory Comput. 13(1): 1-38 (2017) - Chin Ho Lee, Emanuele Viola:
Some Limitations of the Sum of Small-Bias Distributions. Theory Comput. 13(1): 1-23 (2017) - Shachar Lovett:
Additive Combinatorics and its Applications in Theoretical Computer Science. Theory Comput. 8: 1-55 (2017) - Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos:
A Pseudo-Approximation for the Genus of Hamiltonian Graphs. Theory Comput. 13(1): 1-47 (2017) - Cody D. Murray, R. Ryan Williams
:
On the (Non) NP-Hardness of Computing Circuit Complexity. Theory Comput. 13(1): 1-22 (2017) - F. Bruce Shepherd, Adrian R. Vetta:
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems. Theory Comput. 13(1): 1-25 (2017) - Thomas Steinke, Salil P. Vadhan, Andrew Wan:
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs. Theory Comput. 13(1): 1-50 (2017) - 2016
- Nikhil Bansal, Bouke Cloostermans:
Minimizing Maximum Flow-Time on Related Machines. Theory Comput. 12(1): 1-14 (2016)