Articles under category:
Derandomization
Derandomization
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 14, Article 18 (pp 1-45)
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits by Michael A. Forbes, Amir Shpilka, and Ben Lee Volk |
Vol 14, Article 3 (pp 1-21)
[CCC17 Spec Issue]
A Deterministic PTAS for the Commutative Rank of Matrix Spaces by Markus Bläser, Gorav Jindal, and Anurag Pandey |
Vol 13, Article 17 (pp 1-41)
A Constructive Lovász Local Lemma for Permutations by David G. Harris and Aravind Srinivasan |
Vol 13, Article 2 (pp 1-21)
[CCC16 Spec Issue]
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs by Rohit Gurjar, Arpita Korwar, and Nitin Saxena |
Vol 9, Article 30 (pp 897-945)
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream by Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan |
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 |
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 |
Vol 7, Article 12 (pp 177-184)
[NOTE]
On Circuit Lower Bounds from Derandomization by Scott Aaronson and Dieter van Melkebeek |
Vol 4, Article 3 (pp 53-76)
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications by Avi Wigderson and David Xiao |
Vol 3, Article 6 (pp 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman |