Articles under category:
Complexity
Vol 18, Article 17 (pp 1-11) [NOTE]
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
Vol 18, Article 13 (pp 1-65) [RANDOM18 Spec Issue]
Round Complexity Versus Randomness Complexity in Interactive Proofs
by Maya Leshkowitz
Vol 18, Article 12 (pp 1-25)
From Local to Robust Testing via Agreement Testing
by Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
Vol 18, Article 11 (pp 1-49)
Span Programs and Quantum Space Complexity
by Stacey Jeffery
Vol 18, Article 10 (pp 1-12)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines
by Emanuele Viola
Vol 18, Article 4 (pp 1-46) [APRX-RND19 Spec Issue]
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas
by Rocco A. Servedio and Li-Yang Tan
Vol 18, Article 3 (pp 1-29) [APRX-RND16 Spec Issue]
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Vol 18, Article 2 (pp 1-18) [RANDOM18 Spec Issue]
Sunflowers and Robust Sunflowers from Randomness Extractors
by Xin Li, Shachar Lovett, and Jiapeng Zhang
Vol 17, Article 7 (pp 1-46) [APRX-RND19 Spec Issue]
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
Vol 17, Article 4 (pp 1-35) [APRX-RND19 Spec Issue]
Deterministic Approximation of Random Walks in Small Space
by Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Vol 16, Article 13 (pp 1-30)
Monotone Circuit Lower Bounds from Resolution
by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
Vol 16, Article 7 (pp 1-50)
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials
by Chin Ho Lee and Emanuele Viola
Vol 15, Article 17 (pp 1-20)
Separation of AC$^0[\oplus]$ Formulas and Circuits
by Ben Rossman and Srikanth Srinivasan
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Vol 12, Article 9 (pp 1-23) [APRX-RND14 Spec Issue]
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Vol 11, Article 14 (pp 357-393)
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson