Derandomization

Overviews
- Derandomizing complexity classes (Book chapter in Handbook of Randomized Computing, P B Miltersen)
- Recent Developments in Explicit Constructions of Extractors (Ronen Shaltiel)
- Derandomization: A Brief Overview (Vladimir Kabanets (in CC column), 2004)
Courses
- Derandomization (Princeton, 2003, Amit Sahai)
Papers
- Almost Optimal Dispersers (Amnon Ta-Shma, 1998)
- Random Walks, Conditional Hitting Sets and Partial Derandomization (Dimitris A. Fotakis, Paul G. Spirakis, ECCC TR98-049, 1998)
- Extracting Randomness: A Survey and New Constructions (Noam Nisan, Amnon Ta-Shma, 1998)
- 1999
  - Extracting all the Randomness and Reducing the Error in Trevisan's Extractors (Ran Raz, Omer Reingold, Salil Vadhan, 1999)
  - Extractors and Pseudo-Random Generators With Optimal Seed Length ( Russell Impagliazzo, Ronen Shaltiel, et al., 1999)
  - Improved Derandomization of BPP Using a Hitting Set Generator (Oded Goldreich, Avi Wigderson, RANDOM-APPROX 1999)
  - Weak Random Sources, Hitting Sets, and BPP Simulations (Alexander Andreev, Andrea E. F. Clementi, Jose D.P. Rolim, Luca Trevisan, SIAM Journal of Computing, 1999)
  - Derandomizing Arthur-Merlin Games Using Hitting Sets (Peter Bro Miltersen and N.V. Vinodchandran, FOCS 1999)
  - Near-Optimal Conversion of Hardness into Pseudo-Randomness (Impagliazzo, Shaltiel, Wigderson, FOCS 1999)
- 2000
  - Extracting Randomness via Repeated Condensing (Omer Reingold, Ronen Shaltiel, Avi Wigderson, FOCS 2000)
  - Simplified Derandomization of BPP Using a Hitting Set Generator ( Oded Goldreich, Salil Vadhan, Avi Wigderson, ECCC TR00-004, 2000)
- 2001
  - Extractors and Pseudorandom Generators (L Trevisan, 2001)
  - On the Derandomization of Constant Depth Circuits (Adam R. Klivans, RANDOM 2001)
  - Simple polynomially "optimal" HSG
    - Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator
      (R. Shaltiel and C. Umans, FOCS 2001)
- 2002
  - On Constructing Locally Computable Extractors and Cryptosystems In The Bounded Storage Model (Salil Vadhan, 2002)
  - Extractors: Optimal up to Constant Factors (Chi-Jen Lu, Omer Reingold, Salil Vadhan)
  - Graph Nonisomorphism Has Subexponential Size Proofs Unless The Polynomial-Time Hierarchy Collapses (A. Klivans and D. van Melkebeek, SIAM JoC, 2002)
  - Polynomially "optimal" PRG (and HSG)
    - Pseudo-Random Generators for All Hardnesses
      (Chris Umans, STOC/CCC 2002)
- 2003
  - Holographic Proofs and Derandomization (Dieter van Melkebeek, Rahul Santhanam, CCC 2003)
  - Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography (Jesse Kamp, David Zuckerman, FOCS 2003)
- 2004
  - List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument (Cynthia Dwork, Ronen Shaltiel, Adam Smith, and Luca Trevisan, TCC 2004)
  - Some Results on Derandomization (Harry Buhrman, Lance Fortnow, A. Pavan, 2004)
  - Simple Extractors for All Min-Entropies and a New Pseudorandom Generator (Ronen Shaltiel, Christopher Umans, 2004)
  - Extractors with Weak Random Seeds (Ran Raz, ECCC TR04-099)
  - Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed (Ariel Gabizon, Ran Raz, Ronen Shaltiel, FOCS 2004)
- 2005
  - STOC 2005
    - Extractors with Weak Random Seeds
      (Ran Raz, STOC 2005)
    - Derandomization of Auctions
      (Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Jason Hartline, Nicole Immorlica, Madhu Sudan, STOC 2005)
    - Correcting Errors Without Leaking Partial Information
      (Yevgeniy Dodis and Adam Smith, STOC 2005)
    - Simulating independence: New constructions of condensers, Ramsey graphs, dispersers and extractors
      (Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson, STOC 2005)
  - Deterministic Extractors for Affine Sources over Large Fields (Ariel Gabzon, Ran Raz, 2005)
  - Derandomization of PPSZ for Unique-$k$-SAT (Daniel Rolf, ECCC TR05-027)
  - On the Error Parameter of Dispersers, Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma, ECCC TR05-061 (04.06.05)
  - Simple extractors via constructions of cryptographic pseudo-random generators (Marius Zimand, ECCC TR05-071)
  - Derandomized Squaring of Graphs (Eyal Rozenman, Salil Vadhan, ECCC TR05-092)
  - Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number (David Zuckerman, ECCC TR05-100)
  - Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws (Lance Fortnow, John M. Hitchcock, A. Pavan, N.V. Vinodchandran, Fengming Wang, ECCC TR05-105)
  - Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources (Anup Rao, ECCC TR05-106)
  - Deterministic Extractors for Affine Sources over Large Fields (Ariel Gabizon, Ran Raz, ECCC TR05-108)
  - Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed (Ariel Gabizon, Ran Raz, Ronen Shaltiel, ECCC TR05-109)
  - Derandomization in Cryptography (Boaz Barak, Shien Jin Ong, Salil Vadhan, ECCC TR05-114 (full version))
People
- Oded Goldreich (Weizmann)
- Russell Impagliazzo (UC San Diego)
- Adam Klivans (Toyota Technological Institute)
- Dieter van Melkebeek (U Wisconsin Madison)
- Peter Bro Miltersen (Aarhus)
- Noam Nisan (Hebrew U)
- Omer Reingold (Weizmann)
- Ronen Shaltiel (Weizmann)
- Amnon Ta-Shma (Tel-Aviv U)
- Luca Trevisan (UC Berkeley)
- Chris Umans (Caltech)
- Salil Vadhan (Harvard)
- Avi Widgerson (IAS)
@Coding theory links

Cryptology Pointers by Helger Lipmaa
Got any suggestions or additional links? Mail to <lipmaa>research.cyber.ee
NB! If you find any broken links, please be kind and report them to me together with their current location!

(C) Helger Lipmaa 1997-2009.