Articles under category:
Derandomization
Derandomization
|
Vol 20, Article 1 (pp 1-70)
Polynomial Identity Testing via Evaluation of Rational Functions by Ivan Hu, Dieter van Melkebeek, and Andrew Morgan |
|
Vol 19, Article 12 (pp 1-30)
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse |
|
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 |
|
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 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 |