- Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini
, Shachar Lovett:
Pseudorandom Generators from Polarizing Random Walks. Theory Comput. 15: 1-26 (2019) - Shiri Chechik, Ronen Shaltiel:
Special Issue: APPROX-RANDOM 2016: Guest Editors' Foreword. Theory Comput. 15: 1-3 (2019) - Chi-Ning Chou, Mrinal Kumar, Noam Solomon:
Closure Results for Polynomial Factorization. Theory Comput. 15: 1-34 (2019) - Raphaël Clifford, Markus Jalsenius, Benjamin Sach:
Time Bounds for Streaming Problems. Theory Comput. 15: 1-31 (2019) - Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov:
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. Theory Comput. 15: 1-58 (2019) - Anindya De, Elchanan Mossel, Joe Neeman:
Noise Stability is Computable and Approximately Low-Dimensional. Theory Comput. 15: 1-47 (2019) - Zeev Dvir, Benjamin L. Edelman:
Matrix Rigidity and the Croot-Lev-Pach Lemma. Theory Comput. 15: 1-7 (2019) - Fulvio Gesmundo
, Joseph M. Landsberg:
Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives and a Question of K. Mulmuley. Theory Comput. 15: 1-24 (2019) - Timothy Gowers, Oliver Janzer:
Subsets of Cayley Graphs that Induce Many Edges. Theory Comput. 15: 1-29 (2019) - Zeyu Guo
, Nitin Saxena, Amit Sinhababu:
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field. Theory Comput. 15: 1-30 (2019) - Zhengfeng Ji:
Classical Verification of Quantum Proofs. Theory Comput. 15: 1-42 (2019) - Benjamin Rossman, Srikanth Srinivasan
:
Separation of AC0[⊕] Formulas and Circuits. Theory Comput. 15: 1-20 (2019) - Swagato Sanyal:
Fourier Sparsity and Dimension. Theory Comput. 15: 1-13 (2019) - Emanuele Viola:
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds. Theory Comput. 15: 1-9 (2019) - James B. Wilson
:
The Threshold for Subgroup Profiles to Agree is Logarithmic. Theory Comput. 15: 1-25 (2019) - 2018
- Jayadev Acharya, Clément L. Canonne
, Gautam Kamath:
A Chasm Between Identity and Equivalence Testing with Conditional Queries. Theory Comput. 14(1): 1-46 (2018) - Benny Applebaum, Liron David, Guy Even:
Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels. Theory Comput. 14(1): 1-29 (2018) - Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang:
Linear-Time Algorithm for Quantum 2SAT. Theory Comput. 14(1): 1-27 (2018) - Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson:
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits. Theory Comput. 14(1): 1-29 (2018) - Shalev Ben-David, Robin Kothari
:
Randomized Query Complexity of Sabotaged and Composed Functions. Theory Comput. 14(1): 1-27 (2018) - Markus Bläser, Gorav Jindal
, Anurag Pandey:
A Deterministic PTAS for the Commutative Rank of Matrix Spaces. Theory Comput. 14(1): 1-21 (2018) - Anne Broadbent:
How to Verify a Quantum Computation. Theory Comput. 14(1): 1-37 (2018) - Arkadev Chattopadhyay, Nikhil S. Mande
:
Separation of Unbounded-Error Models in Multi-Party Communication Complexity. Theory Comput. 14(1): 1-23 (2018) - Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Theory Comput. 14(1): 1-55 (2018) - Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li:
Trading Information Complexity for Error. Theory Comput. 14(1): 1-73 (2018) - Yfke Dulek, Christian Schaffner
, Florian Speelman
:
Quantum Homomorphic Encryption for Polynomial-Size Circuits. Theory Comput. 14(1): 1-45 (2018) - Michael A. Forbes, Amir Shpilka
, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. Theory Comput. 14(1): 1-45 (2018) - Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems. Theory Comput. 14(1): 1-33 (2018) - Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree. Theory Comput. 14(1): 1-46 (2018) - Swastik Kopparty, Srikanth Srinivasan
:
Certifying Polynomials for $\mathrm{AC}0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression. Theory Comput. 14(1): 1-24 (2018)