Computational applications of noise sensitivity
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2003.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/29354 |
| _version_ | 1826217981050355712 |
|---|---|
| author | O'Donnell, Ryan William, 1979- |
| author2 | Madhu Sudan. |
| author_facet | Madhu Sudan. O'Donnell, Ryan William, 1979- |
| author_sort | O'Donnell, Ryan William, 1979- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2003. |
| first_indexed | 2024-09-23T17:12:15Z |
| format | Thesis |
| id | mit-1721.1/29354 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T17:12:15Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/293542019-04-12T09:42:22Z Computational applications of noise sensitivity O'Donnell, Ryan William, 1979- Madhu Sudan. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2003. Includes bibliographical references (p. 161-171). This thesis is concerned with the study of the noise sensitivity of boolean functions and its applications in theoretical computer science. Noise sensitivity is defined as follows: Let f be a boolean function and let ... be a parameter. Suppose a uniformly random string x is picked, and y is formed by flipping each bit of x independently with probability e. Then the noise sensitivity of f at e is defined to be the probability that f(x) and f(y) differ. In this thesis we investigate the noise sensitivity of various classes of boolean functions, including majorities and recursive majorities, boolean threshold functions, and monotone functions. Following this we give new complexity-theoretic and algorithmic applications of noise sensitivity: * Regarding computational hardness amplification, we prove a general direct product theorem that tightly characterizes the hardness of a composite function g 9 f in terms of an assumed hardness of f and the noise sensitivity of g. The theorem lets us prove a new result about the hardness on average of NP: If NP is (1 - poly(n))-hard for circuits of polynomial size, then it is in fact (1/2 + o(1))-hard for circuits of polynomial size. * In the field of computational learning theory, we show that any class whose functions have low noise sensitivity is efficiently learnable. Using our noise sensitivity estimates for functions of boolean halfspaces we obtain new polynomial and quasipolynomial time algorithms for learning intersections, thresholds, and other functions of halfspaces. (cont.) From noise sensitivity considerations we also give a polynomial time algorithm for learning polynomial-sized DNFs under the "Random Walk" model; we also give the first algorithm that learns the class of "junta" functions with efficiency better than that of the brute force algorithm. * Finally, we introduce a new collective coin-flipping problem whose study is equivalent to the study of "higher moments" of the noise sensitivity problem. We prove several results about this extension, and find optimal or near-optimal choices for the coin-flipping function for all asymptotic limits of the parameters. Our techniques include a novel application of the reverse Bonami-Beckner inequality. by Ryan William O'Donnell. Ph.D. 2005-10-14T20:02:00Z 2005-10-14T20:02:00Z 2003 2003 Thesis http://hdl.handle.net/1721.1/29354 52769218 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 171 p. 6317774 bytes 6317579 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. O'Donnell, Ryan William, 1979- Computational applications of noise sensitivity |
| title | Computational applications of noise sensitivity |
| title_full | Computational applications of noise sensitivity |
| title_fullStr | Computational applications of noise sensitivity |
| title_full_unstemmed | Computational applications of noise sensitivity |
| title_short | Computational applications of noise sensitivity |
| title_sort | computational applications of noise sensitivity |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/29354 |
| work_keys_str_mv | AT odonnellryanwilliam1979 computationalapplicationsofnoisesensitivity |