Articles under category:
RANDOM
RANDOM
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 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 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 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 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 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 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 17, Article 7 (pp 1-46)
[APRX-RND19 Spec Issue]
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
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
Deterministic Approximation of Random Walks in Small Space
by Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Vol 17, Article 3 (pp 1-4)
[APRX-RND19 Spec Issue]
Special Issue: APPROX-RANDOM 2019: Guest Editors' Foreword
by Noga Ron-Zewi, Ivona Bezáková, and László Végh
Special Issue: APPROX-RANDOM 2019: Guest Editors' Foreword
by Noga Ron-Zewi, Ivona Bezáková, and László Végh
Vol 15, Article 15 (pp 1-58)
[APRX-RND16 Spec Issue]
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
by Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
by Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov
Vol 15, Article 14 (pp 1-3)
[APRX-RND16 Spec Issue]
Special Issue: APPROX-RANDOM 2016: Guest Editors' Foreword
by Shiri Chechik and Ronen Shaltiel
Special Issue: APPROX-RANDOM 2016: Guest Editors' Foreword
by Shiri Chechik and Ronen Shaltiel
Vol 13, Article 14 (pp 1-17)
[APRX-RND15 Spec Issue]
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
by David Felber and Rafail Ostrovsky
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
by David Felber and Rafail Ostrovsky
Vol 13, Article 12 (pp 1-50)
[APRX-RND14 Spec Issue]
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
by Thomas Steinke, Salil Vadhan, and Andrew Wan
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
by Thomas Steinke, Salil Vadhan, and Andrew Wan
Vol 13, Article 8 (pp 1-22)
[APRX-RND15 Spec Issue]
The Minimum Bisection in the Planted Bisection Model
by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
The Minimum Bisection in the Planted Bisection Model
by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
Vol 12, Article 13 (pp 1-3)
[APRX-RND15 Spec Issue]
Special Issue: APPROX-RANDOM 2015: Guest Editors' Foreword
by Nicole Megow and Mary Wootters
Special Issue: APPROX-RANDOM 2015: Guest Editors' Foreword
by Nicole Megow and Mary Wootters
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
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Vol 12, Article 8 (pp 1-3)
[APRX-RND14 Spec Issue]
Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword
by Deeparnab Chakrabarty and David Galvin
Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword
by Deeparnab Chakrabarty and David Galvin
Vol 12, Article 1 (pp 1-61)
[APRX-RND13 Spec Issue]
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
by Amos Beimel, Kobbi Nissim, and Uri Stemmer
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
by Amos Beimel, Kobbi Nissim, and Uri Stemmer
Vol 11, Article 17 (pp 413-443)
[APRX-RND13 Spec Issue]
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration
by Emmanuel Abbe and Andrea Montanari
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration
by Emmanuel Abbe and Andrea Montanari
Vol 11, Article 12 (pp 299-338)
[APRX-RND13 Spec Issue]
Absolutely Sound Testing of Lifted Codes
by Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan
Absolutely Sound Testing of Lifted Codes
by Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan
Vol 11, Article 8 (pp 237-239)
[APRX-RND13 Spec Issue]
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword
by Sofya Raskhodnikova and Ola Svensson
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword
by Sofya Raskhodnikova and Ola Svensson
Vol 9, Article 25 (pp 783-807)
[APRX-RND12 Spec Issue]
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes
by Noga Ron-Zewi and Madhu Sudan
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes
by Noga Ron-Zewi and Madhu Sudan
Vol 9, Article 15 (pp 559-577)
[APRX-RND12 Spec Issue]
Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions
by Noga Alon and Shachar Lovett
Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions
by Noga Alon and Shachar Lovett
Vol 9, Article 13 (pp 441-470)
[APRX-RND12 Spec Issue]
Optimal Hitting Sets for Combinatorial Shapes
by Aditya Bhaskara, Devendra Desai, and Srikanth Srinivasan
Optimal Hitting Sets for Combinatorial Shapes
by Aditya Bhaskara, Devendra Desai, and Srikanth Srinivasan
Vol 9, Article 12 (pp 437-439)
[APRX-RND12 Spec Issue]
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword
by Alexandr Andoni and Atri Rudra
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword
by Alexandr Andoni and Atri Rudra