Amnon Ta-Shma:

Refining Randomness

Download

Abstract This work presents two new theorems concerning randomness, and low-space classes:

• The first part of the thesis presents two new constructions of explicit extractors. Extractors are strong expanders and have been proven extremely useful in derandomization tasks. However, it is not known how to explicitly construct optimal extractors. We significantly improve previous results and achieve almost optimal extractors that work for sources with small entropy and extract all of the randomness from the given source. We are also able to improve previous applications by plugging in our new extractors to previous constructions.
• The second part of the thesis is a theorem showing that the class SL, containing all languages LogSpace reducible to the undirected s,t connectivity problem, is closed under complement. This also shows that two hierarchies that were built upon SL collapse to SL, and therefore several important problems, as 2-colorability, are actually solvable in SL.

  Table of Contents

     
  
  
  1. Introduction........................   1
  2. Explicit Extractors.................. 23
  3. SL=coSL.............................. 79
  Bibliography............................ 90
  Appendix................................ 99