Volume 18 (2022)
Vol 18, Article 1 (pp 1-3)
[RANDOM18 Spec Issue]
Special Issue: RANDOM 2018: Guest Editor's Foreword by Andrew Drucker |
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 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 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 5 (pp 1-28)
[CCC19 Spec Issue]
UG-hardness to NP-hardness by Losing Half by Amey Bhangale and Subhash Khot |
Vol 18, Article 6 (pp 1-33)
[APRX-RND19 Spec Issue]
Max-Min Greedy Matching by Alon Eden, Uriel Feige, and Michal Feldman |
Vol 18, Article 7 (pp 1-24)
[APRX-RND19 Spec Issue]
Fast and Deterministic Approximations for $k$-Cut by Kent Quanrud |
Vol 18, Article 8 (pp 1-18)
[CCC18 Spec Issue]
The Cayley Semigroup Membership Problem by Lukas Fleischer |
Vol 18, Article 9 (pp 1-18)
[APRX-RND19 Spec Issue]
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions by Zongchen Chen and Santosh S. Vempala |
Vol 18, Article 10 (pp 1-12)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines by Emanuele Viola |
Vol 18, Article 11 (pp 1-49)
Span Programs and Quantum Space Complexity by Stacey Jeffery |
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 13 (pp 1-65)
[RANDOM18 Spec Issue]
Round Complexity Versus Randomness Complexity in Interactive Proofs by Maya Leshkowitz |
Vol 18, Article 14 (pp 1-4)
[CCC20 Spec Issue]
Special Issue: CCC 2020: Guest Editors' Foreword by Zeev Dvir and Avishay Tal |
Vol 18, Article 15 (pp 1-33)
[CCC20 Spec Issue]
Multiparty Karchmer-Wigderson Games and Threshold Circuits by Alexander Kozachinskiy and Vladimir Podolskii |
Vol 18, Article 16 (pp 1-54)
Tensor Network Complexity of Multilinear Maps by Per Austrin, Petteri Kaski, and Kaie Kubjas |
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 18 (pp 1-19)
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks by Chandra Chekuri and Tanmay Inamdar |
Vol 18, Article 19 (pp 1-22)
[CCC20 Spec Issue]
Sign-Rank vs. Discrepancy by Kaave Hosseini, Hamed Hatami, and Shachar Lovett |
Vol 18, Article 20 (pp 1-32)
Universal Streaming of Subset Norms by Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang |
Vol 18, Article 21 (pp 1-32)
[CCC20 Spec Issue]
Hitting Sets Give Two-Sided Derandomization of Small Space by Kuan Cheng and William M. Hoza |
Vol 18, Article 22 (pp 1-22)
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications by Alexander Golovnev and Ishay Haviv |
Vol 18, Article 23 (pp 1-24)
Pure Entropic Regularization for Metrical Task Systems by Christian Coester and James R. Lee |
List of Editors |