Volume 18 (2022)
Vol 18, Article 1 (pp 1-3)
[RANDOM18 Spec Issue]
Special Issue: RANDOM 2018: Guest Editor's Foreword
by Andrew Drucker
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
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
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
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
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
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
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
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
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
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines
by Emanuele Viola
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
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
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
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
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
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
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
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
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
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
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
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
Pure Entropic Regularization for Metrical Task Systems
by Christian Coester and James R. Lee