Applications of unconditional pseudorandomness in complexity theory
by Healy, Alexander D., Ph.D., HARVARD UNIVERSITY, 2007, 156 pages; 3264977
 Abstract: Pseudorandomness—that is, information that "appears random" even though it is generated using very little true randomness—is a fundamental notion in cryptography and complexity theory. This thesis explores the applications of pseudorandomness within complexity theory, with a focus on pseudorandomness that can be constructed unconditionally, that is without relying on any unproven complexity assumptions. Such pseudorandomness only "fools" restricted classes of algorithms, and yet it can be applied to prove complexity results that concern very general models of computation. For instance, we show the following: (1)  Randomness-Efficient Error Reduction for Parallel Algorithms. Typically, to gain confidence in a randomized algorithm, one repeats the algorithm several times (with independent randomness) and takes the majority vote of the executions. While very effective, this is wasteful in terms of the number of random bits that are used. Randomness-efficient error reduction techniques are known for polynomial-time algorithms, but do not readily apply to parallel algorithms since the techniques seem inherently sequential. We achieve randomness-efficient error reduction for highly-parallel algorithms. Specifically, we can reduce the error of a parallel algorithm to any δ > 0 while paying only O(log(1/δ)) additional random bits, thereby matching the results for polynomial-time. (2) Hardness Amplification within NP. A fundamental question in average-case complexity is whether P ≠ NP implies the existence of functions in NP that are hard on average (over randomly-chosen inputs). While the answer to this question seems far beyond the reach of current techniques, we show that powerful hardness amplification is indeed feasible within NP. In particular, we show that if NP has a mildly hard-on-average function f (i.e., any small circuit for computing f fails on at least a constant fraction of inputs), then NP has a function f' that is extremely hard on average (i.e., any small circuit for computing f' only succeeds with exponentially-small advantage over random guessing). Previous results only obtained functions f' that could not be computed with polynomial advantage over random guessing. Our stronger results are obtained by using derandomization and nondeterminism in constructing f'. A common theme in our results is the computational efficiency of pseudorandom generators. Indeed, our results both rely upon, and enable us to construct pseudorandom generators that can be computed very efficiently (in terms of parallel complexity).

 Adviser Michael O. Rabin School HARVARD UNIVERSITY Source DAI/B 68-05, p. , Aug 2007 Source Type Dissertation Subjects Computer science Publication Number 3264977
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3264977 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).

About ProQuest Dissertations & Theses
With over 2.3 million records, the ProQuest Dissertations & Theses (PQDT) database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

The database includes citations of graduate works ranging from the first U.S. dissertation, accepted in 1861, to those accepted as recently as last semester. Of the 2.3 million graduate works included in the database, ProQuest offers more than 1.9 million in full text formats. Of those, over 860,000 are available in PDF format. More than 60,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or call ProQuest Hotline Customer Support at 1-800-521-3042.