Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Favorite Theorem: Connections

Expand Messages
  • Lance
    May Edition I have always loved results that find connections between previously-thought different areas of complexity. This month we highlight one of the
    Message 1 of 1 , Jun 11, 2004
    • 0 Attachment
      May Edition

      I have always loved results that find connections between previously-thought different areas of complexity. This month we highlight one of the best.

      Extractors and Pseudorandom Generators by Luca Trevisan

      Informally a pseudorandom generator takes a small random seed and generates strings that can fool every probabilistic algorithm. To describe an extractor we start with some distribution D over strings of length n. Let p be the maximum probability of any string in D and let k = log(1/p). An extractor uses D and a small number of truly random bits to create a new uniform distribution of strings of length close to k.

      Both pseudorandom generators and extractors have many uses in complexity and many papers in the field show various constructions to improve the parameters of both. Trevisan showed that one can view any pseudorandom generator as an extractor and then derives better extractors from known pseudorandom generator constructions.

      Pseudorandom generators fools resource-bounded algorithms while extractors nearly uniform distributions in an information-theoretic sense. That makes this connection all the more amazing. Trevisan's paper has affected the how researchers think about and prove results in both areas.

      --
      Posted by Lance to My Computational Complexity Web Log at 6/11/2004 08:53:31 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.