Computational applications of noise sensitivity

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2003

Author dc:creator

• O'Donnell, Ryan William, 1979-

Advisor dc:contributor.advisor

• Madhu Sudan.

• Mathematics.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/29354

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/29354