Volume 19 (2023)
Vol 19, Article 1 (pp 1-48)
Sublinear-Time Computation in the Presence of Online Erasures
by Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma
Sublinear-Time Computation in the Presence of Online Erasures
by Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma
Vol 19, Article 2 (pp 1-23)
On Solving Reachability in Grid Digraphs using a Pseudoseparator
by Rahul Jain and Raghunath Tewari
On Solving Reachability in Grid Digraphs using a Pseudoseparator
by Rahul Jain and Raghunath Tewari
Vol 19, Article 3 (pp 1-56)
Exponentially Small Soundness for the Direct Product Z-test
by Irit Dinur and Inbal Livni Navon
Exponentially Small Soundness for the Direct Product Z-test
by Irit Dinur and Inbal Livni Navon
Vol 19, Article 4 (pp 1-61)
[CCC20 Spec Issue]
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
by Shuichi Hirahara
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
by Shuichi Hirahara
Vol 19, Article 5 (pp 1-3)
[APRX-RND20 Spec Issue]
Special Issue: APPROX-RANDOM 2020: Guest Editor's Foreword
by Jarosław Byrka and Raghu Meka
Special Issue: APPROX-RANDOM 2020: Guest Editor's Foreword
by Jarosław Byrka and Raghu Meka
Vol 19, Article 6 (pp 1-21)
[APRX-RND20 Spec Issue]
Reaching a Consensus on Random Networks: The Power of Few
by Linh Tran and Van Vu
Reaching a Consensus on Random Networks: The Power of Few
by Linh Tran and Van Vu
Vol 19, Article 7 (pp 1-51)
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by Yuval Filmus, Or Meir, and Avishay Tal
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by Yuval Filmus, Or Meir, and Avishay Tal
Vol 19, Article 8 (pp 1-71)
[APRX-RND20 Spec Issue]
Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
by Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
by Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
Vol 19, Article 9 (pp 1-35)
Optimal Composition Theorem for Randomized Query Complexity
by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal
Optimal Composition Theorem for Randomized Query Complexity
by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal
Vol 19, Article 10 (pp 1-44)
Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams
by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang
Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams
by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang
Vol 19, Article 11 (pp 1-14)
A Strong XOR Lemma for Randomized Query Complexity
by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu
A Strong XOR Lemma for Randomized Query Complexity
by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu
Vol 19, Article 12 (pp 1-30)
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse