- Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan:
Deterministic Approximation of Random Walks in Small Space. Theory Comput. 17: 1-35 (2021) - Ryan O'Donnell, Tselil Schramm:
Sherali-Adams Strikes Back. Theory Comput. 17: 1-30 (2021) - Igor C. Oliveira, Ján Pich, Rahul Santhanam:
Hardness Magnification Near State-of-the-Art Lower Bounds. Theory Comput. 17: 1-38 (2021) - Noga Ron-Zewi, Ivona Bezáková, László A. Végh:
Special Issue: APPROX-RANDOM 2019: Guest Editors' Foreword. Theory Comput. 17: 1-4 (2021) - 2020
- Scott Aaronson, Sam Gunn:
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. Theory Comput. 16: 1-8 (2020) - Noga Alon, Elchanan Mossel, Robin Pemantle:
Distributed Corruption Detection in Networks. Theory Comput. 16: 1-23 (2020) - Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor
, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Theory Comput. 16: 1-36 (2020) - Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan:
Optimality of Correlated Sampling Strategies. Theory Comput. 16: 1-18 (2020) - Amey Bhangale, Prahladh Harsha, Girish Varma:
A Characterization of Hard-to-Cover CSPs. Theory Comput. 16: 1-30 (2020) - Andrej Bogdanov, Siyao Guo, Ilan Komargodski:
Threshold Secret Sharing Requires a Linear-Size Alphabet. Theory Comput. 16: 1-18 (2020) - Mark Bun, Robin Kothari
, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. 16: 1-71 (2020) - Chandra Chekuri, Shi Li:
On the Hardness of Approximating the k-Way Hypergraph Cut problem. Theory Comput. 16: 1-8 (2020) - Lijie Chen:
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Theory Comput. 16: 1-50 (2020) - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. Theory Comput. 16: 1-34 (2020) - Michael B. Cohen, Cameron Musco, Jakub Pachocki:
Online Row Sampling. Theory Comput. 16: 1-25 (2020) - Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Sharp Bounds for Population Recovery. Theory Comput. 16: 1-20 (2020) - Zeev Dvir, Allen Liu:
Fourier and Circulant Matrices are Not Rigid. Theory Comput. 16: 1-48 (2020) - Yuval Filmus:
Special Issue: CCC 2019: Guest Editor's Foreword. Theory Comput. 16: 1-5 (2020) - Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
:
Monotone Circuit Lower Bounds from Resolution. Theory Comput. 16: 1-30 (2020) - Parikshit Gopalan, Amir Yehudayoff:
Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials. Theory Comput. 16: 1-29 (2020) - Tom Gur, Govind Ramnarayan, Ron Rothblum:
Relaxed Locally Correctable Codes. Theory Comput. 16: 1-68 (2020) - Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil P. Vadhan, Hoeteck Wee:
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing. Theory Comput. 16: 1-55 (2020) - Pavel Hrubes:
On the Complexity of Computing a Random Boolean Function Over the Reals. Theory Comput. 16: 1-12 (2020) - Chin Ho Lee, Emanuele Viola:
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials. Theory Comput. 16: 1-50 (2020) - 2019
- Srikanth Srinivasan
:
Special Issue: CCC 2018: Guest Editor's Foreword. Theory Comput. 15: 1-3 (2019) - Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, S. Raja:
Randomized Polynomial-Time Identity Testing for Noncommutative Circuits. Theory Comput. 15: 1-36 (2019) - Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett:
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. Theory Comput. 15: 1-27 (2019) - Nikhil Bansal, Anupam Gupta
:
Potential-Function Proofs for Gradient Methods. Theory Comput. 15: 1-32 (2019) - Jop Briët, Zeev Dvir, Sivakanth Gopi:
Outlaw Distributions and Locally Decodable Codes. Theory Comput. 15: 1-24 (2019) - Clément L. Canonne
, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer:
Testing k-Monotonicity: The Rise and Fall of Boolean Functions. Theory Comput. 15: 1-55 (2019)