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
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
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
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
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
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
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
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
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
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
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
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 7, Article 12 (pp 177-184)
[NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
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
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
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman