Noise correlation bounds for uniform low degree functions

Per Austrin Department of Computer Science, University of Toronto Elchanan Mossel University of California, Berkeley, 367 Evans Hall, Berkeley, CA, U.S.A.

Combinatorics Optimization and Control mathscidoc:1701.06003

Arkiv for Matematik, 51, (1), 29-52, 2010.8
We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by$δ$are called$δ$-$uniform$. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics.
No keywords uploaded!
[ Download ] [ 2017-01-08 20:36:33 uploaded by arkivadmin ] [ 966 downloads ] [ 0 comments ]
  title={Noise correlation bounds for uniform low degree functions},
  author={Per Austrin, and Elchanan Mossel},
  booktitle={Arkiv for Matematik},
Per Austrin, and Elchanan Mossel. Noise correlation bounds for uniform low degree functions. 2010. Vol. 51. In Arkiv for Matematik. pp.29-52.
Please log in for comment!
Contact us: | Copyright Reserved