Articles under category:
Complexity
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 |