Noise stability of functions with low influences: Invariance and optimality

Abstract

In this paper we study functions with low influences on product probability spaces. These are functions $f : \Omega_1 \times \cdots \times \Omega_n \to\mathbb{R}$ that have ${\rm E}[{\rm Var}_{\Omega_i}[f]]$ small compared to ${\rm Var}[f]$ for each $i$. The analysis of boolean functions $f: \{-1,1\}^n \to \{-1,1\}$ with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics.

We prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions the distribution of such polynomials is essentially invariant for all product spaces. Ours is one of the very few known nonlinear invariance principles. It has the advantage that its proof is simple and that its error bounds are explicit. We also show that the assumption of bounded degree can be eliminated if the polynomials are slightly “smoothed”; this extension is essential for our applications to “noise stability”-type problems.

In particular, as applications of the invariance principle we prove two conjectures: Khot, Kindler, Mossel, and O’Donnell’s “Majority Is Stablest” conjecture from theoretical computer science, which was the original motivation for this work, and Kalai and Friedgut’s “It Ain’t Over Till It’s Over” conjecture from social choice theory.

  • [AlDiFrSu:04] Go to document N. Alon, I. Dinur, E. Friedgut, and B. Sudakov, "Graph products, Fourier analysis and spectral techniques," Geom. Funct. Anal., vol. 14, iss. 5, pp. 913-940, 2004.
    @article{AlDiFrSu:04, MRKEY = {2105948},
      AUTHOR = {Alon, N. and Dinur, I. and Friedgut, E. and Sudakov, B.},
      TITLE = {Graph products, {F}ourier analysis and spectral techniques},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {14},
      YEAR = {2004},
      NUMBER = {5},
      PAGES = {913--940},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {05C69 (42A16)},
      MRNUMBER = {2005i:05131},
      DOI = {10.1007/s00039-004-0478-3},
      ZBLNUMBER = {1056.05104},
      MRREVIEWER = {Richard C. Brewster},
      }
  • [Aus07a] Go to document P. Austrin, "Balanced Max 2-Sat might not be the hardest," in Proc. 39th Ann. ACM Symposium on Theory of Computing, Johnson, D. S. and Feige, U., Eds., New York: ACM, 2007, pp. 189-197.
    @incollection{Aus07a, MRKEY = {2402442},
      AUTHOR = {Austrin, Per},
      EDITOR = {Johnson, David S. and Feige, Uriel},
      TITLE = {Balanced {M}ax 2-{S}at might not be the hardest},
      BOOKTITLE = {{P}roc. 39th {A}nn. {ACM} {S}ymposium on {T}heory of {C}omputing},
      VENUE = {San Diego, CA, 2007},
      PAGES = {189--197},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2007},
      DOI = {10.1145/1250790.1250818},
      MRCLASS = {68Q17},
      MRNUMBER = {2402442},
      ZBLNUMBER={pre05485451},
      }
  • [Aus07b] Go to document P. Austrin, "Towards sharp inapproximability for any 2-CSP," in Proc. 48th Ann. Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 2007, pp. 307-317.
    @incollection{Aus07b,
      author = {Austrin, Per},
      TITLE = {Towards sharp inapproximability for any 2-{CSP}},
      BOOKTITLE = {Proc. 48th Ann. Foundations of Computer Science},
      YEAR = {2007},
      PUBLISHER = {IEEE Computer Society},
      ADDRESS = {Los Alamitos, CA},
      pages = {307--317},
      DOI = {10.1109/FOCS.2007.41},
      MRNUMBER={2500340},
      }
  • [AustrinMossel:08] Go to document P. Austrin and E. Mossel, "Approximation resistant predicates from pairwise independence," in Proceedings of Conference on Computational Complexity 2008, Los Alamitos, CA: IEEE Computer Society, 2008, pp. 249-258.
    @incollection{AustrinMossel:08,
      author = {Austrin, Per and Mossel, Elchanan},
      TITLE = {Approximation resistant predicates from pairwise independence},
      BOOKTITLE = {Proceedings of Conference on Computational Complexity 2008},
      YEAR = {2008},
      PUBLISHER = {IEEE Computer Society},
      ADDRESS = {Los Alamitos, CA},
      pages = {249--258},
      DOI = {10.1109/CCC.2008.20},
      MRNUMBER={2500340},
      }
  • [Bakry:94] D. Bakry, R. D. Gill, and S. A. Molchanov, Lectures on probability theory, New York: Springer-Verlag, 1994.
    @book{Bakry:94, MRKEY = {1307412},
      AUTHOR = {Bakry, D. and Gill, R. D. and Molchanov, S. A.},
      TITLE = {Lectures on probability theory},
      SERIES = {Lecture Notes in Mathematics},
      NUMBER = {1581},
      INVNOTE = {Lectures from the Twenty-second Saint-Flour Summer School held July 9--25, 1992, Edited by P. Bernard},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1994},
      PAGES = {viii+419},
      ISBN = {3-540-58208-8},
      MRCLASS = {60-06 (00B25)},
      MRNUMBER = {95f:60004},
      ZBLNUMBER = {0797.00021},
      }
  • [Beckner:75] Go to document W. Beckner, "Inequalities in Fourier analysis," Ann. of Math., vol. 102, iss. 1, pp. 159-182, 1975.
    @article{Beckner:75, MRKEY = {0385456},
      AUTHOR = {Beckner, William},
      TITLE = {Inequalities in {F}ourier analysis},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {102},
      YEAR = {1975},
      NUMBER = {1},
      PAGES = {159--182},
      ISSN = {0003-486X},
      MRCLASS = {42A92 (42A18)},
      MRNUMBER = {52 \#6317},
      DOI = {10.2307/1970980},
      ZBLNUMBER = {0338.42017},
      MRREVIEWER = {I. I. Hirschman, Jr.},
      }
  • [Beckner:92] W. Beckner, "Sobolev inequalities, the Poisson semigroup, and analysis on the sphere $S^n$," Proc. Nat. Acad. Science U.S.A., vol. 89, iss. 11, pp. 4816-4819, 1992.
    @article{Beckner:92, MRKEY = {1164616},
      AUTHOR = {Beckner, William},
      TITLE = {Sobolev inequalities, the {P}oisson semigroup, and analysis on the sphere {$S\sp n$}},
      JOURNAL = {Proc. Nat. Acad. Science U.S.A.},
      FJOURNAL = {Proceedings of the National Academy of Sciences of the United States of America},
      VOLUME = {89},
      YEAR = {1992},
      NUMBER = {11},
      PAGES = {4816--4819},
      ISSN = {0027-8424},
      CODEN = {PNASA6},
      MRCLASS = {26D15 (26A33 43A85 46E35 47D03 47N99)},
      MRNUMBER = {93d:26018},
      ZBLNUMBER = {0766.46012},
      MRREVIEWER = {Gerald B. Folland},
      }
  • [BenorLinial:90] M. Ben-Or and N. Linial, "Collective coin flipping," in Randomness and Computation, S. Micali, Ed., New York: Academic Press, 1990.
    @incollection{BenorLinial:90,
      author = {M. Ben-Or and N. Linial},
      TITLE = { Collective coin flipping},
      EDITOR = {S.~Micali},
      BOOKTITLE ={Randomness and Computation},
      PUBLISHER = {Academic Press},
      ADDRESS = {New York},
      YEAR = {1990},
      ZBLNUMBER={0675.90107},
      }
  • [BeKaSc:99] Go to document I. Benjamini, G. Kalai, and O. Schramm, "Noise sensitivity of Boolean functions and applications to percolation," Inst. Hautes Études Sci. Publ. Math., iss. 90, pp. 5-43 (2001), 1999.
    @article{BeKaSc:99, MRKEY = {1813223},
      AUTHOR = {Benjamini, Itai and Kalai, Gil and Schramm, Oded},
      TITLE = {Noise sensitivity of {B}oolean functions and applications to percolation},
      JOURNAL = {Inst. Hautes Études Sci. Publ. Math.},
      FJOURNAL = {Institut des Hautes Études Scientifiques. Publications Mathématiques},
      NUMBER = {90},
      YEAR = {1999},
      PAGES = {5--43 (2001)},
      ISSN = {0073-8301},
      CODEN = {PMIHA6},
      MRCLASS = {60B15 (60K35 68Q15 82B43 94C10)},
      MRNUMBER = {2001m:60016},
      URL = {http://www.numdam.org/item?id=PMIHES_1999__90__5_0},
      ZBLNUMBER = {0986.60002},
      MRREVIEWER = {H. Kesten},
      }
  • [Bernasconi:98] A. Bernasconi, "Mathematical techniques for the analysis of Boolean functions," PhD Thesis , Institute for Computational Mathematics, Pisa, 1998.
    @phdthesis{Bernasconi:98,
      author = {A.~Bernasconi},
      TITLE = {Mathematical techniques for the analysis of Boolean functions},
      TYPE = {thesis},
      SCHOOL = {Institute for Computational Mathematics, Pisa},
      YEAR = {1998},
      }
  • [Bobkov:97] Go to document S. G. Bobkov, "An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space," Ann. Probab., vol. 25, iss. 1, pp. 206-214, 1997.
    @article{Bobkov:97, MRKEY = {1428506},
      AUTHOR = {Bobkov, S. G.},
      TITLE = {An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in {G}auss space},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {25},
      YEAR = {1997},
      NUMBER = {1},
      PAGES = {206--214},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60E15 (60G15)},
      MRNUMBER = {98g:60033},
      DOI = {10.1214/aop/1024404285},
      ZBLNUMBER = {0883.60031},
      MRREVIEWER = {Werner Linde},
      }
  • [Bonami:70] Go to document A. Bonami, "Étude des coefficients de Fourier des fonctions de $L^{p}(G)$," Ann. Instit. Fourier $($Univ. Grenoble$)$, vol. 20, iss. fasc. 2, pp. 335-402 (1971), 1970.
    @article{Bonami:70, MRKEY = {0283496},
      AUTHOR = {Bonami, Aline},
      TITLE = {\'{E}tude des coefficients de {F}ourier des fonctions de {$L\sp{p}(G)$}},
      JOURNAL = {Ann. Instit. Fourier $($Univ. Grenoble$)$},
      FJOURNAL = {Université de Grenoble. Annales de l'Institut Fourier},
      VOLUME = {20},
      YEAR = {1970},
      NUMBER = {fasc. 2},
      PAGES = {335--402 (1971)},
      ISSN = {0373-0956},
      MRCLASS = {42.50},
      MRNUMBER = {44 \#727},
      URL = {http://www.numdam.org/item?id=AIF_1970__20_2_335_0},
      ZBLNUMBER = {0195.42501},
      MRREVIEWER = {S. Izumi},
      }
  • [Borell:82] Go to document C. Borell, "Positivity improving operators and hypercontractivity," Math. Z., vol. 180, iss. 2, pp. 225-234, 1982.
    @article{Borell:82, MRKEY = {661699},
      AUTHOR = {Borell, Christer},
      TITLE = {Positivity improving operators and hypercontractivity},
      JOURNAL = {Math. Z.},
      FJOURNAL = {Mathematische Zeitschrift},
      VOLUME = {180},
      YEAR = {1982},
      NUMBER = {2},
      PAGES = {225--234},
      ISSN = {0025-5874},
      CODEN = {MAZEAX},
      MRCLASS = {47B25 (47E05 81E10)},
      MRNUMBER = {84b:47029},
      DOI = {10.1007/BF01318906},
      ZBLNUMBER = {0472.47015},
      MRREVIEWER = {R. Høegh-Krohn},
      }
  • [Borell:85] Go to document C. Borell, "Geometric bounds on the Ornstein-Uhlenbeck velocity process," Z. Wahrsch. Verw. Gebiete, vol. 70, iss. 1, pp. 1-13, 1985.
    @article{Borell:85, MRKEY = {795785},
      AUTHOR = {Borell, Christer},
      TITLE = {Geometric bounds on the {O}rnstein-{U}hlenbeck velocity process},
      JOURNAL = {Z. Wahrsch. Verw. Gebiete},
      FJOURNAL = {Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete},
      VOLUME = {70},
      YEAR = {1985},
      NUMBER = {1},
      PAGES = {1--13},
      ISSN = {0044-3719},
      CODEN = {ZWVGAA},
      MRCLASS = {60G15 (60G40)},
      MRNUMBER = {87k:60103},
      DOI = {10.1007/BF00532234},
      ZBLNUMBER = {0537.60084},
      MRREVIEWER = {Michael Cranston},
      }
  • [Bourgain:99] J. Bourgain, , 1999.
    @misc{Bourgain:99, MRKEY = {1678031},
      AUTHOR = {J. Bourgain},
      TITLE = {},
      howpublished = {appendix to \cite{Friedgut:99}},
      YEAR = {1999},
      }
  • [Bourgain:02] Go to document J. Bourgain, "On the distributions of the Fourier spectrum of Boolean functions," Israel J. Math., vol. 131, pp. 269-276, 2002.
    @article{Bourgain:02, MRKEY = {1942312},
      AUTHOR = {Bourgain, J.},
      TITLE = {On the distributions of the {F}ourier spectrum of {B}oolean functions},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {131},
      YEAR = {2002},
      PAGES = {269--276},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {43A75 (42A38)},
      MRNUMBER = {2003j:43009},
      DOI = {10.1007/BF02785861},
      MRREVIEWER = {Colin C. Graham},
      ZBLNUMBER = {1021.43004},
      }
  • [BK:97] Go to document J. Bourgain and G. Kalai, "Influences of variables and threshold intervals under group symmetries," Geom. Funct. Anal., vol. 7, iss. 3, pp. 438-461, 1997.
    @article{BK:97, MRKEY = {1466334},
      AUTHOR = {Bourgain, J. and Kalai, G.},
      TITLE = {Influences of variables and threshold intervals under group symmetries},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {7},
      YEAR = {1997},
      NUMBER = {3},
      PAGES = {438--461},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {20B35 (05C80 20B15)},
      MRNUMBER = {98j:20005},
      DOI = {10.1007/s000390050015},
      ZBLNUMBER = {0982.20004},
      MRREVIEWER = {Wolfgang Lusky},
      }
  • [CarberyWright:01] A. Carbery and J. Wright, "Distributional and $L^q$ norm inequalities for polynomials over convex bodies in $\mathbb{R}^n$," Math. Res. Lett., vol. 8, iss. 3, pp. 233-248, 2001.
    @article{CarberyWright:01, MRKEY = {1839474},
      AUTHOR = {Carbery, Anthony and Wright, James},
      TITLE = {Distributional and {$L\sp q$} norm inequalities for polynomials over convex bodies in {$\mathbb{R}\sp n$}},
      JOURNAL = {Math. Res. Lett.},
      FJOURNAL = {Mathematical Research Letters},
      VOLUME = {8},
      YEAR = {2001},
      NUMBER = {3},
      PAGES = {233--248},
      ISSN = {1073-2780},
      MRCLASS = {26D15 (42B20 46E30)},
      MRNUMBER = {2002h:26033},
      ZBLNUMBER = {0989.26010},
      MRREVIEWER = {Lars Erik Persson},
      }
  • [Chatterjee:u] S. Chatterjee, "A simple invariance theorem," , preprint , 2005.
    @techreport{Chatterjee:u,
      author = {S. Chatterjee},
      TITLE = {A simple invariance theorem},
      TYPE = {preprint},
      ARXIV = {math/0508213v1},
      YEAR = {2005},
      }
  • [CKKRS:05] Go to document S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar, "On the hardness of approximating Multicut and Sparsest-Cut," Comput. Complexity, vol. 15, iss. 2, pp. 94-114, 2006.
    @article{CKKRS:05, MRKEY = {2243123},
      AUTHOR = {Chawla, Shuchi and Krauthgamer, Robert and Kumar, Ravi and Rabani, Yuval and Sivakumar, D.},
      TITLE = {On the hardness of approximating {M}ulticut and {S}parsest-{C}ut},
      JOURNAL = {Comput. Complexity},
      FJOURNAL = {Computational Complexity},
      VOLUME = {15},
      YEAR = {2006},
      NUMBER = {2},
      PAGES = {94--114},
      ISSN = {1016-3328},
      CODEN = {CPTCEU},
      MRCLASS = {68Q17 (90C60)},
      MRNUMBER = {2008a:68074},
      DOI = {10.1007/s00037-006-0210-9},
      ZBLNUMBER = {1132.68418},
      }
  • [dKPaWa:04] Go to document E. de Klerk, D. V. Pasechnik, and J. P. Warners, "On approximate graph colouring and MAX-$k$-CUT algorithms based on the $\vartheta$-function," J. Comb. Optim., vol. 8, iss. 3, pp. 267-294, 2004.
    @article{dKPaWa:04, MRKEY = {2092261},
      AUTHOR = {de Klerk, E. and Pasechnik, D. V. and Warners, J. P.},
      TITLE = {On approximate graph colouring and {MAX}-{$k$}-{CUT} algorithms based on the {$\vartheta$}-function},
      JOURNAL = {J. Comb. Optim.},
      FJOURNAL = {Journal of Combinatorial Optimization},
      VOLUME = {8},
      YEAR = {2004},
      NUMBER = {3},
      PAGES = {267--294},
      ISSN = {1382-6905},
      MRCLASS = {68W25 (05C15 05C85 90C09 90C22 90C27)},
      MRNUMBER = {2005h:68184},
      DOI = {10.1023/B:JOCO.0000038911.67280.3f},
      ZBLNUMBER = {1084.68142},
      MRREVIEWER = {Mark R. Jerrum},
      }
  • [DinurFriedgut] Go to document I. Dinur and E. Friedgut, "Intersecting families are essentially contained in juntas," , preprint , 2008.
    @techreport{DinurFriedgut,
      author = {I. Dinur and E. Friedgut},
      TITLE = {Intersecting families are essentially contained in juntas},
      TYPE = {preprint},
      YEAR = {2008},
      URL = {http://www.ma.huji.ac.il/~ehudf/docs/intersecting1.pdf},
      }
  • [DiFrKiOD:07] Go to document I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell, "On the Fourier tails of bounded functions over the discrete cube," Israel J. Math., vol. 160, pp. 389-412, 2007.
    @article{DiFrKiOD:07, MRKEY = {2342503},
      AUTHOR = {Dinur, Irit and Friedgut, Ehud and Kindler, Guy and O'Donnell, Ryan},
      TITLE = {On the {F}ourier tails of bounded functions over the discrete cube},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {160},
      YEAR = {2007},
      PAGES = {389--412},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {43A75 (60C05)},
      MRNUMBER = {2342503},
      DOI = {10.1007/s11856-007-0068-9},
      MRREVIEWER = {Wolfgang Lusky},
      ZBLNUMBER = {05256344},
      }
  • [DGKO:05] Go to document I. Dinur, V. Guruswami, S. Khot, and O. Regev, "A new multilayered PCP and the hardness of hypergraph vertex cover," SIAM J. Comput., vol. 34, iss. 5, pp. 1129-1146, 2005.
    @article{DGKO:05, MRKEY = {2164979},
      AUTHOR = {Dinur, Irit and Guruswami, Venkatesan and Khot, Subhash and Regev, Oded},
      TITLE = {A new multilayered {PCP} and the hardness of hypergraph vertex cover},
      JOURNAL = {{\rm SIAM} J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {34},
      YEAR = {2005},
      NUMBER = {5},
      PAGES = {1129--1146},
      ISSN = {0097-5397},
      MRCLASS = {68Q15 (68Q17)},
      MRNUMBER = {2006e:68046},
      DOI = {10.1137/S0097539704443057},
      ZBLNUMBER = {1079.68039},
      MRREVIEWER = {Johan H{\aa}stad},
      }
  • [DinurMosselRegev:06] Go to document I. Dinur, E. Mossel, and O. Regev, "Conditional hardness for approximate coloring," in Proc. 38th Annual ACM Symposium on Theory of Computing, Kleinberg, J. M., Ed., New York: ACM, 2006, pp. 344-353.
    @incollection{DinurMosselRegev:06, MRKEY = {2277160},
      AUTHOR = {Dinur, Irit and Mossel, Elchanan and Regev, Oded},
      EDITOR = {Jon M. Kleinberg},
      TITLE = {Conditional hardness for approximate coloring},
      BOOKTITLE = {{P}roc. 38th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      VENUE = {Seattle, 2006},
      PAGES = {344--353},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2006},
      MRCLASS = {68Q17 (05C15)},
      MRNUMBER = {2007h:68069},
      DOI = {10.1145/1132516.1132567},
      ISBN = {1-59593-134-1},
      }
  • [DinurSafra:05] Go to document I. Dinur and S. Safra, "On the hardness of approximating minimum vertex cover," Ann. of Math., vol. 162, iss. 1, pp. 439-485, 2005.
    @article{DinurSafra:05, MRKEY = {2178966},
      AUTHOR = {Dinur, Irit and Safra, Samuel},
      TITLE = {On the hardness of approximating minimum vertex cover},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {162},
      YEAR = {2005},
      NUMBER = {1},
      PAGES = {439--485},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {68Q17 (68Q15)},
      MRNUMBER = {2006e:68054},
      URL = {http://projecteuclid.org/getRecord?id=euclid.annm/1134073588},
      ZBLNUMBER = {1084.68051},
      MRREVIEWER = {Johan H{\aa}stad},
      }
  • [DoGrLe:96] R. Dobrushin, P. Groeneboom, and M. Ledoux, Lectures on probability theory and statistics, New York: Springer-Verlag, 1996.
    @book{DoGrLe:96, MRKEY = {1600892},
      AUTHOR = {Dobrushin, R. and Groeneboom, P. and Ledoux, M.},
      TITLE = {Lectures on probability theory and statistics},
      SERIES = {Lecture Notes in Math.},
      NUMBER = {1648},
      INVNOTE = {Lectures from the 24th Saint-Flour Summer School held July 7--23, 1994, Edited by P. Bernard},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1996},
      PAGES = {viii+300},
      ISBN = {3-540-62055-9},
      MRCLASS = {60-06 (62-06)},
      MRNUMBER = {98g:60002},
      ZBLNUMBER = {0855.00026},
      }
  • [Edgar:75] Go to document G. A. Edgar, "A noncompact Choquet theorem," Proc. Amer. Math. Soc., vol. 49, pp. 354-358, 1975.
    @article{Edgar:75, MRKEY = {0372586},
      AUTHOR = {Edgar, G. A.},
      TITLE = {A noncompact {C}hoquet theorem},
      JOURNAL = {Proc. Amer. Math. Soc.},
      FJOURNAL = {Proceedings of the American Mathematical Society},
      VOLUME = {49},
      YEAR = {1975},
      PAGES = {354--358},
      ISSN = {0002-9939},
      MRCLASS = {46B05},
      MRNUMBER = {51 \#8793},
      DOI = {10.2307/2040645},
      ZBLNUMBER = {0273.46012},
      MRREVIEWER = {Benno Fuchssteiner},
      }
  • [FeigeSchechtman:02] Go to document U. Feige and G. Schechtman, "On the optimality of the random hyperplane rounding technique for MAX CUT: Probabilistic methods in combinatorial optimization," Random Structures Algorithms, vol. 20, iss. 3, pp. 403-440, 2002.
    @article{FeigeSchechtman:02, MRKEY = {1900615},
      AUTHOR = {Feige, Uriel and Schechtman, Gideon},
      TITLE = {On the optimality of the random hyperplane rounding technique for {MAX} {CUT}: {P}robabilistic methods in combinatorial optimization},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {20},
      YEAR = {2002},
      NUMBER = {3},
      PAGES = {403--440},
      ISSN = {1042-9832},
      MRCLASS = {90C27 (05C85 90C57)},
      MRNUMBER = {2003c:90086},
      DOI = {10.1002/rsa.10036},
      ZBLNUMBER = {1005.90052},
      }
  • [Feller:71] W. Feller, An introduction to probability theory and its applications, II, 2nd ed., New York: Wiley, 1971.
    @book{Feller:71, MRKEY = {0270403},
      AUTHOR = {Feller, William},
      TITLE = {An introduction to probability theory and its applications, {\rm II}},
      EDITION = {2nd},
      PUBLISHER = {Wiley},
      ADDRESS = {New York},
      YEAR = {1971},
      PAGES = {xxiv+669},
      MRCLASS = {60.00},
      MRNUMBER = {42 \#5292},
      ZBLNUMBER = {0219.60003},
      }
  • [FelsenthalMachover:98] D. S. Felsenthal and M. Machover, The measurement of voting power: Theory and practice, problems and paradoxes, Cheltenham: Edward Elgar, 1998.
    @book{FelsenthalMachover:98, MRKEY = {1761929},
      AUTHOR = {Felsenthal, Dan S. and Machover, Mosh{é}},
      TITLE = {The measurement of voting power: {T}heory and practice, problems and paradoxes},
      PUBLISHER = {Edward Elgar},
      FPUBLISHER = {Edward Elgar Publishing Limited},
      ADDRESS = {Cheltenham},
      YEAR = {1998},
      PAGES = {xviii+322},
      ISBN = {1-85898-805-5},
      MRCLASS = {91B12 (91-02 91A12)},
      MRNUMBER = {2001h:91032},
      ZBLNUMBER = {0954.91019},
      MRREVIEWER = {Maurice Salles},
      }
  • [Friedgut:98] Go to document E. Friedgut, "Boolean functions with low average sensitivity depend on few coordinates," Combinatorica, vol. 18, iss. 1, pp. 27-35, 1998.
    @article{Friedgut:98, MRKEY = {1645642},
      AUTHOR = {Friedgut, Ehud},
      TITLE = {Boolean functions with low average sensitivity depend on few coordinates},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {18},
      YEAR = {1998},
      NUMBER = {1},
      PAGES = {27--35},
      ISSN = {0209-9683},
      MRCLASS = {28A99 (05A16 05C80 28A60)},
      MRNUMBER = {99g:28021},
      DOI = {10.1007/PL00009809},
      ZBLNUMBER = {0909.06008},
      }
  • [Friedgut:99] Go to document E. Friedgut, "Sharp thresholds of graph properties, and the $k$-sat problem," J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999.
    @article{Friedgut:99, MRKEY = {1678031},
      AUTHOR = {Friedgut, Ehud},
      TITLE = {Sharp thresholds of graph properties, and the {$k$}-sat problem},
      INVNOTE = {With an appendix by Jean Bourgain},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {12},
      YEAR = {1999},
      NUMBER = {4},
      PAGES = {1017--1054},
      ISSN = {0894-0347},
      MRCLASS = {05C80 (42C10)},
      MRNUMBER = {2000a:05183},
      DOI = {10.1090/S0894-0347-99-00305-7},
      ZBLNUMBER = {0932.05084},
      MRREVIEWER = {Mark R. Jerrum},
      }
  • [FriedgutKalai:96] Go to document E. Friedgut and G. Kalai, "Every monotone graph property has a sharp threshold," Proc. Amer. Math. Soc., vol. 124, iss. 10, pp. 2993-3002, 1996.
    @article{FriedgutKalai:96, MRKEY = {1371123},
      AUTHOR = {Friedgut, Ehud and Kalai, Gil},
      TITLE = {Every monotone graph property has a sharp threshold},
      JOURNAL = {Proc. Amer. Math. Soc.},
      FJOURNAL = {Proceedings of the American Mathematical Society},
      VOLUME = {124},
      YEAR = {1996},
      NUMBER = {10},
      PAGES = {2993--3002},
      ISSN = {0002-9939},
      CODEN = {PAMYAR},
      MRCLASS = {05C80},
      MRNUMBER = {97e:05172},
      DOI = {10.1090/S0002-9939-96-03732-X},
      ZBLNUMBER = {0864.05078},
      MRREVIEWER = {Andrzej Ruci{ń}ski},
      }
  • [FrKaNa:02] Go to document E. Friedgut, G. Kalai, and A. Naor, "Boolean functions whose Fourier transform is concentrated on the first two levels," Adv. in Appl. Math., vol. 29, iss. 3, pp. 427-437, 2002.
    @article{FrKaNa:02, MRKEY = {1942632},
      AUTHOR = {Friedgut, Ehud and Kalai, Gil and Naor, Assaf},
      TITLE = {Boolean functions whose {F}ourier transform is concentrated on the first two levels},
      JOURNAL = {Adv. in Appl. Math.},
      FJOURNAL = {Advances in Applied Mathematics},
      VOLUME = {29},
      YEAR = {2002},
      NUMBER = {3},
      PAGES = {427--437},
      ISSN = {0196-8858},
      MRCLASS = {26D07 (42B10 94C10)},
      MRNUMBER = {2003j:26011},
      DOI = {10.1016/S0196-8858(02)00024-6},
      ZBLNUMBER = {1039.91014},
      MRREVIEWER = {Eduard Belinskii},
      }
  • [GamkrelidzeRotar:77] N. G. Gamkrelidze and V. I. Rotarcprime, "The rate of convergence in a limit theorem for quadratic forms," Teor. Verojatnost. i Primenen., vol. 22, iss. 2, pp. 404-407, 1977.
    @article{GamkrelidzeRotar:77, MRKEY = {0443040},
      AUTHOR = {Gamkrelidze, N. G. and Rotar{\cprime},
      V. I.},
      TITLE = {The rate of convergence in a limit theorem for quadratic forms},
      JOURNAL = {Teor. Verojatnost. i Primenen.},
      FJOURNAL = {Akademija Nauk SSSR. Teorija Verojatnosteĭi ee Primenenija},
      VOLUME = {22},
      YEAR = {1977},
      NUMBER = {2},
      PAGES = {404--407},
      ISSN = {0040-361x},
      MRCLASS = {60F05},
      MRNUMBER = {56 \#1413},
      ZBLNUMBER = {0385.60035},
      MRREVIEWER = {V. L. Girko},
      NOTE = {In Russian; translated in \emph{Theory Probab. Appl.} {\bf 22} (1977), 394--397}
    }
  • [GoemansWilliamson:95] Go to document M. X. Goemans and D. P. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming," J. Assoc. Comput. Mach., vol. 42, iss. 6, pp. 1115-1145, 1995.
    @article{GoemansWilliamson:95, MRKEY = {1412228},
      AUTHOR = {Goemans, Michel X. and Williamson, David P.},
      TITLE = {Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming},
      JOURNAL = {J. Assoc. Comput. Mach.},
      FJOURNAL = {Journal of the Association for Computing Machinery},
      VOLUME = {42},
      YEAR = {1995},
      NUMBER = {6},
      PAGES = {1115--1145},
      ISSN = {0004-5411},
      CODEN = {JACOAH},
      MRCLASS = {90C27 (68Q25 90C35)},
      MRNUMBER = {97g:90108},
      DOI = {10.1145/227683.227684},
      ZBLNUMBER = {0885.68088},
      MRREVIEWER = {Nikolay N. Ivanov},
      }
  • [GotzeTikhomirov:05] Go to document F. Götze and A. N. Tikhomirov, "Asymptotic expansions in non-central limit theorems for quadratic forms," J. Theoret. Probab., vol. 18, iss. 4, pp. 757-811, 2005.
    @article{GotzeTikhomirov:05, MRKEY = {2289931},
      AUTHOR = {G{ö}tze, F. and Tikhomirov, A. N.},
      TITLE = {Asymptotic expansions in non-central limit theorems for quadratic forms},
      JOURNAL = {J. Theoret. Probab.},
      FJOURNAL = {Journal of Theoretical Probability},
      VOLUME = {18},
      YEAR = {2005},
      NUMBER = {4},
      PAGES = {757--811},
      ISSN = {0894-9840},
      CODEN = {JTPREO},
      MRCLASS = {60E15 (60F05)},
      MRNUMBER = {2008e:60042},
      DOI = {10.1007/s10959-005-7525-3},
      MRREVIEWER = {Peter Eichelsbacher},
      ZBLNUMBER = {1089.60017},
      }
  • [Janson:97] S. Janson, Gaussian Hilbert spaces, Cambridge: Cambridge Univ. Press, 1997.
    @book{Janson:97, MRKEY = {1474726},
      AUTHOR = {Janson, Svante},
      TITLE = {Gaussian {H}ilbert spaces},
      SERIES = {Cambridge Tracts in Mathematics},
      NUMBER = {129},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1997},
      PAGES = {x+340},
      ISBN = {0-521-56128-0},
      MRCLASS = {60G35 (60H15 62M20 81T08)},
      MRNUMBER = {99f:60082},
      ZBLNUMBER = {0887.60009},
      MRREVIEWER = {Amarjit Budhiraja},
      }
  • [KaKaLi:88] Go to document J. Kahn, G. Kalai, and N. Linial, "The influence of variables on boolean functions," in Proc. 29th Ann. IEEE Symposium on Foundations of Computer Science, Washington, DC: IEEE Computer Society, 1988, pp. 68-80.
    @incollection{KaKaLi:88,
      author = {J. Kahn and G. Kalai and N. Linial},
      TITLE = {The influence of variables on boolean functions},
      DOI = {10.1109/SFCS.1988.21923},
      BOOKTITLE = {Proc. 29th {A}nn. {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience},
      VENUE = {White Plains, NY, 1988},
      PUBLISHER = {IEEE Computer Society},
      FPUBLISHER = {IEEE Computer Society Press},
      ADDRESS = {Washington, DC},
      pages = {68--80},
      YEAR = {1988},
      }
  • [Kalai:02] Go to document G. Kalai, "A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem," Adv. in Appl. Math., vol. 29, iss. 3, pp. 412-426, 2002.
    @article{Kalai:02, MRKEY = {1942631},
      AUTHOR = {Kalai, Gil},
      TITLE = {A {F}ourier-theoretic perspective on the {C}ondorcet paradox and {A}rrow's theorem},
      JOURNAL = {Adv. in Appl. Math.},
      FJOURNAL = {Advances in Applied Mathematics},
      VOLUME = {29},
      YEAR = {2002},
      NUMBER = {3},
      PAGES = {412--426},
      ISSN = {0196-8858},
      MRCLASS = {91B14 (42C10 91B08 91B12)},
      MRNUMBER = {2003h:91046},
      DOI = {10.1016/S0196-8858(02)00023-4},
      ZBLNUMBER = {1038.91027},
      MRREVIEWER = {Marco LiCalzi},
      }
  • [Kalai:04] Go to document G. Kalai, "Social indeterminacy," Econometrica, vol. 72, iss. 5, pp. 1565-1581, 2004.
    @article{Kalai:04, MRKEY = {2078213},
      AUTHOR = {Kalai, Gil},
      TITLE = {Social indeterminacy},
      JOURNAL = {Econometrica},
      FJOURNAL = {Econometrica. Journal of the Econometric Society},
      VOLUME = {72},
      YEAR = {2004},
      NUMBER = {5},
      PAGES = {1565--1581},
      ISSN = {0012-9682},
      CODEN = {ECMTA7},
      MRCLASS = {91B12 (91A12 91B14)},
      MRNUMBER = {2005d:91034},
      DOI = {10.1111/j.1468-0262.2004.00543.x},
      ZBLNUMBER = {1141.91373},
      MRREVIEWER = {Fouad T. Aleskerov},
      }
  • [Kalai:01] G. Kalai and E. Friedgut, "It Ain’t Over Till It’s Over," , personal communication , 2006.
    @techreport{Kalai:01,
      author = {Kalai, Gil and E. Friedgut},
      TITLE = {It {A}in't {O}ver {T}ill {I}t's {O}ver},
      TYPE = {personal communication},
      year=2006, }
  • [Katz:63] Go to document M. L. Katz, "Note on the Berry-Esseen theorem," Ann. Math. Statist., vol. 34, pp. 1107-1108, 1963.
    @article{Katz:63, MRKEY = {0151996},
      AUTHOR = {Katz, Melvin L.},
      TITLE = {Note on the {B}erry-{E}sseen theorem},
      JOURNAL = {Ann. Math. Statist.},
      FJOURNAL = {Annals of Mathematical Statistics},
      VOLUME = {34},
      YEAR = {1963},
      PAGES = {1107--1108},
      ISSN = {0003-4851},
      MRCLASS = {60.30},
      MRNUMBER = {27 \#1977},
      DOI = {10.1214/aoms/1177704037},
      ZBLNUMBER = {0122.36704},
      MRREVIEWER = {C. G. Esseen},
      }
  • [Khot:02] Go to document S. Khot, "On the power of unique 2-prover 1-round games," in Proc. 34th Ann. ACM Symposium on Theory of Computing, New York: ACM, 2002, pp. 767-775.
    @incollection{Khot:02, MRKEY = {2121525},
      AUTHOR = {Khot, Subhash},
      TITLE = {On the power of unique 2-prover 1-round games},
      BOOKTITLE = {Proc. 34th {A}nn. {\rm ACM} {S}ymposium on {T}heory of {C}omputing},
      VENUE = {Montreal, 2002},
      PAGES = {767--775},
      URL = {http://portal.acm.org/toc.cfm?id=509907},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2002},
      MRCLASS = {68Q25 (68Q15)},
      MRNUMBER = {2121525},
      }
  • [KKMO:07] Go to document S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, "Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?," SIAM J. Comput., vol. 37, iss. 1, pp. 319-357, 2007.
    @article{KKMO:07, MRKEY = {2306295},
      AUTHOR = {Khot, Subhash and Kindler, Guy and Mossel, Elchanan and O'Donnell, Ryan},
      TITLE = {Optimal inapproximability results for {MAX}-{CUT} and other 2-variable {CSP}s?},
      JOURNAL = {{\rm SIAM} J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {37},
      YEAR = {2007},
      NUMBER = {1},
      PAGES = {319--357},
      ISSN = {0097-5397},
      MRCLASS = {68Q17},
      MRNUMBER = {2008d:68035},
      DOI = {10.1137/S0097539705447372},
      ZBLNUMBER = {1135.68019},
      MRREVIEWER = {J{ö}rg Rothe},
      }
  • [KhotRegev:03] Go to document S. Khot and O. Regev, "Vertex cover might be hard to approximate to within $2-\epsilon$," J. Comput. System Sci., vol. 74, iss. 3, pp. 335-349, 2008.
    @article{KhotRegev:03, MRKEY = {2384079},
      AUTHOR = {Khot, Subhash and Regev, Oded},
      TITLE = {Vertex cover might be hard to approximate to within {$2-\epsilon$}},
      JOURNAL = {J. Comput. System Sci.},
      FJOURNAL = {Journal of Computer and System Sciences},
      VOLUME = {74},
      YEAR = {2008},
      NUMBER = {3},
      PAGES = {335--349},
      ISSN = {0022-0000},
      CODEN = {JCSSBM},
      MRCLASS = {68Q17 (05C65 05C70 05C85 91A43)},
      MRNUMBER = {2384079},
      DOI = {10.1016/j.jcss.2007.06.019},
      ZBLNUMBER = {1133.68061},
      }
  • [KhotVishnoi:05] Go to document S. Khot and N. Vishnoi, "The Unique Games Conjecture: Integrality gap for cut problems and embeddability of negative type metrics into $\ell_1$," in Proc. 46th Ann. Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 2005, pp. 53-62.
    @incollection{KhotVishnoi:05,
      author = {S. Khot and N. Vishnoi},
      TITLE = {The {U}nique {G}ames {C}onjecture: {I}ntegrality gap for cut problems and embeddability of negative type metrics into $\ell_1$},
      BOOKTITLE = {Proc. 46th Ann. Foundations of Computer Science},
      VENUE = {Pittsburgh, 2005},
      PUBLISHER = {IEEE Computer Society},
      DOI = {10.1109/SFCS.2005.74},
      ADDRESS = {Los Alamitos, CA},
      pages = {53--62},
      YEAR = {2005},
      }
  • [KindlerSafra:u] Go to document G. Kindler and S. Safra, "Noise-resistant boolean functions are juntas," , preprint , 2003.
    @techreport{KindlerSafra:u,
      author = {G. Kindler and S. Safra},
      TITLE = {Noise-resistant boolean functions are juntas},
      TYPE = {preprint},
      YEAR = {2003},
      URL = {http://www.cs.tau.ac.il/~safra/PapersAndTalks/nibfj.ps},
      }
  • [KrakowiakSzulga:88] Go to document W. Krakowiak and J. Szulga, "Hypercontraction principle and random multilinear forms," Probability Theory and Related Fields, vol. 77, iss. 3, pp. 325-342, 1988.
    @article{KrakowiakSzulga:88, MRKEY = {931501},
      AUTHOR = {Krakowiak, Wies{\l}aw and Szulga, Jerzy},
      TITLE = {Hypercontraction principle and random multilinear forms},
      JOURNAL = {Probability Theory and Related Fields},
      FJOURNAL = {Probability Theory and Related Fields},
      VOLUME = {77},
      YEAR = {1988},
      NUMBER = {3},
      PAGES = {325--342},
      ISSN = {0178-8051},
      CODEN = {PTRFEU},
      MRCLASS = {60B11 (60G42)},
      MRNUMBER = {90e:60007},
      DOI = {10.1007/BF00319292},
      ZBLNUMBER = {0621.60004},
      MRREVIEWER = {Autorreferat},
      }
  • [KwapienWoyczynski:92] S. Kwapień and W. A. Woyczyński, Random series and stochastic integrals: Single and multiple, Boston: Birkhäuser, 1992.
    @book{KwapienWoyczynski:92, MRKEY = {1167198},
      AUTHOR = {Kwapie{ń},
      Stanis{\l}aw and Woyczy{ń}ski, Wojbor A.},
      TITLE = {Random series and stochastic integrals: {S}ingle and multiple},
      SERIES = {Probability and its Applications},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston},
      YEAR = {1992},
      PAGES = {xvi+360},
      ISBN = {0-8176-3572-6},
      MRCLASS = {60G48 (60B11 60E15 60G42 60G50 60G57 60H05)},
      MRNUMBER = {94k:60074},
      ZBLNUMBER = {0751.60035},
      MRREVIEWER = {Jerzy Szulga},
      }
  • [LedouxTalagrand:91] M. Ledoux and M. Talagrand, Probability in Banach spaces: Isoperimetry and processes, New York: Springer-Verlag, 1991.
    @book{LedouxTalagrand:91, MRKEY = {1102015},
      AUTHOR = {Ledoux, Michel and Talagrand, Michel},
      TITLE = {Probability in {B}anach spaces: {I}soperimetry and processes},
      SERIES = {Ergeb. Math. Grenzgeb.},
      NUMBER = {23},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1991},
      PAGES = {xii+480},
      ISBN = {3-540-52013-9},
      MRCLASS = {60-02 (60Bxx 60Fxx 60Gxx)},
      MRNUMBER = {93c:60001},
      ZBLNUMBER = {0748.60004},
      MRREVIEWER = {Evarist Gin{é}},
      }
  • [Lindeberg:22] Go to document J. W. Lindeberg, "Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung," Math Z., vol. 15, pp. 211-225, 1922.
    @article{Lindeberg:22,
      author = {Lindeberg, J. W.},
      TITLE = {Eine neue {H}erleitung des {E}xponentialgesetzes in der {W}ahrscheinlichkeitsrechnung},
      JOURNAL = {Math Z.},
      FJOURNAL = {J. Math Zeitschrift},
      VOLUME = {15},
      YEAR = {1922},
      PAGES = {211--225},
      URL = {http://resolver.sub.uni-goettingen.de/purl?GDZPPN002367076},
      JFMNUMBER = {48.0602.04},
      MRNUMBER={1544569},
      }
  • [Mossel:08] E. Mossel, "Gaussian bounds for noise correlation of functions," , preprint , 2008.
    @techreport{Mossel:08,
      author = {E. Mossel},
      TITLE = {Gaussian bounds for noise correlation of functions},
      TYPE= {preprint},
      ARXIV = {math/0703683v4},
      YEAR = {2008},
      }
  • [MOO:focs] Go to document E. Mossel, R. O’Donnell, and K. Oleszkiewicz, "Noise stability of functions with low influences: Invariance and optimality," in Proc. 46th Ann. Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 2005, pp. 21-30.
    @incollection{MOO:focs,
      author = {E. Mossel and R. O'Donnell and K.~Oleszkiewicz},
      TITLE = {Noise stability of functions with low influences: {I}nvariance and optimality},
      BOOKTITLE = {Proc. 46th Ann. Foundations of Computer Science},
      VENUE = {Pittsburgh, 2005},
      PUBLISHER = {IEEE Computer Society},
      ADDRESS = {Los Alamitos, CA},
      DOI = {10.1109/SFCS.2005.53},
      PAGES = {21--30},
      YEAR = {2005},
      }
  • [MORSS:06] Go to document E. Mossel, R. O’Donnell, O. Regev, J. E. Steif, and B. Sudakov, "Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality," Israel J. Math., vol. 154, pp. 299-336, 2006.
    @article{MORSS:06, MRKEY = {2254545},
      AUTHOR = {Mossel, Elchanan and O'Donnell, Ryan and Regev, Oded and Steif, Jeffrey E. and Sudakov, Benny},
      TITLE = {Non-interactive correlation distillation, inhomogeneous {M}arkov chains, and the reverse {B}onami-{B}eckner inequality},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {154},
      YEAR = {2006},
      PAGES = {299--336},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {60C05 (60J10)},
      MRNUMBER = {2008b:60018},
      DOI = {10.1007/BF02773611},
      ZBLNUMBER = {1140.60007},
      MRREVIEWER = {Johan H{\aa}stad},
      }
  • [OWu07a] Go to document R. O’Donnell and Y. Wu, "An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests," in Proc. 40th Ann. ACM Symposium on Theory of Computing, Ladner, R. E. and Dwork, C., Eds., New York: ACM, 2007, pp. 335-344.
    @incollection{OWu07a,
      author = {R. O'Donnell and Y. Wu},
      editor = {Richard E. Ladner and Cynthia Dwork},
      TITLE ={An optimal {SDP} algorithm for {Max-Cut},
      and equally optimal {Long} {Code} tests},
      BOOKTITLE = {Proc. 40th {A}nn. {ACM} {S}ymposium on {T}heory of {C}omputing},
      VENUE = {Victoria, BC, 2008},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      year = {2007},
      DOI = {10.1145/1374376.1374425},
      PAGES = {335--344}
    }
  • [Oleszkiewicz:03] K. Oleszkiewicz, "On a nonsymmetric version of the Khinchine–Kahane inequality," in Stochastic inequalities and applications, Basel: Birkhäuser, 2003, pp. 157-168.
    @incollection{Oleszkiewicz:03, MRKEY = {2073432},
      AUTHOR = {Oleszkiewicz, Krzysztof},
      TITLE = {On a nonsymmetric version of the {K}hinchine--{K}ahane inequality},
      BOOKTITLE = {Stochastic inequalities and applications},
      SERIES = {Progr. Prob.},
      NUMBER = {56},
      PAGES = {157--168},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Basel},
      YEAR = {2003},
      MRCLASS = {60E15 (46B09)},
      MRNUMBER = {2005f:60049},
      ZBLNUMBER = {1043.46017},
      MRREVIEWER = {Stefan Geiss},
      }
  • [Petrov:75] V. V. Petrov, Sums of independent random variables, New York: Springer-Verlag, 1975.
    @book{Petrov:75, MRKEY = {0388499},
      AUTHOR = {Petrov, V. V.},
      TITLE = {Sums of independent random variables},
      INVNOTE = {Translated from the Russian by A. A. Brown},
      SERIES = {Ergeb. Math. Grenzgeb.},
      NUMBER = {82},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1975},
      PAGES = {x+346},
      MRCLASS = {60FXX (60GXX)},
      MRNUMBER = {52 \#9335},
      ZBLNUMBER = {0322.60043},
      }
  • [Raghavendra:08] Go to document P. Raghvendra, "Optimal algorithms and inapproximability results for every CSP?," in Proc. 40th Ann. ACM Symposium on Theory of Computing, Ladner, R. E. and Dwork, C., Eds., New York: ACM, 2008, pp. 245-254.
    @incollection{Raghavendra:08,
      author = {P. Raghvendra},
      editor = {Richard E. Ladner and Cynthia Dwork},
      TITLE = {Optimal algorithms and inapproximability results for every {CSP}?},
      BOOKTITLE = {Proc. 40th {A}nn. {ACM} {S}ymposium on {T}heory of {C}omputing},
      VENUE = {Victoria, BC, 2008},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      pages = {245--254},
      YEAR = {2008},
      DOI = {10.1145/1374376.1374414},
      }
  • [RinotRotar:01] Go to document Y. Rinott and V. Rotar, "A remark on quadrant normal probabilities in high dimensions," Statist. Probab. Lett., vol. 51, iss. 1, pp. 47-51, 2001.
    @article{RinotRotar:01, MRKEY = {1820144},
      AUTHOR = {Rinott, Yosef and Rotar, Vladimir},
      TITLE = {A remark on quadrant normal probabilities in high dimensions},
      JOURNAL = {Statist. Probab. Lett.},
      FJOURNAL = {Statistics \& Probability Letters},
      VOLUME = {51},
      YEAR = {2001},
      NUMBER = {1},
      PAGES = {47--51},
      ISSN = {0167-7152},
      CODEN = {SPLTDC},
      MRCLASS = {62E20 (60E05 91A15)},
      MRNUMBER = {2002a:62013},
      DOI = {10.1016/S0167-7152(00)00141-3},
      ZBLNUMBER = {0979.62006},
      MRREVIEWER = {Satish Iyengar},
      }
  • [Rotar:75] V. I. Rotarcprime, "Limit theorems for multilinear forms and quasipolynomial functions," Teor. Verojatnost. i Primenen., vol. 20, iss. 3, pp. 527-546, 1975.
    @article{Rotar:75, MRKEY = {0385980},
      AUTHOR = {Rotar{\cprime},
      V. I.},
      TITLE = {Limit theorems for multilinear forms and quasipolynomial functions},
      JOURNAL = {Teor. Verojatnost. i Primenen.},
      FJOURNAL = {Akademija Nauk SSSR. Teorija Verojatnosteĭi ee Primenenija},
      VOLUME = {20},
      YEAR = {1975},
      NUMBER = {3},
      PAGES = {527--546},
      ISSN = {0040-361x},
      MRCLASS = {60F05},
      MRNUMBER = {52 \#6839},
      MRREVIEWER = {V. L. Girko},
      ZBLNUMBER = {0372.60030},
      }
  • [Rotar:79] Go to document V. I. Rotarcprime, "Limit theorems for polylinear forms," J. Multivariate Anal., vol. 9, iss. 4, pp. 511-530, 1979.
    @article{Rotar:79, MRKEY = {556909},
      AUTHOR = {Rotar{\cprime},
      V. I.},
      TITLE = {Limit theorems for polylinear forms},
      JOURNAL = {J. Multivariate Anal.},
      FJOURNAL = {Journal of Multivariate Analysis},
      VOLUME = {9},
      YEAR = {1979},
      NUMBER = {4},
      PAGES = {511--530},
      ISSN = {0047-259X},
      CODEN = {JMVAAI},
      MRCLASS = {60F05 (62H10)},
      MRNUMBER = {81m:60039},
      DOI = {10.1016/0047-259X(79)90055-1},
      MRREVIEWER = {V. L. Girko},
      ZBLNUMBER = {0426.62013},
      }
  • [ST:06] Go to document A. Samorodnitsky and L. Trevisan, "Gowers uniformity, influence of variables, and PCPs," in Proc. 38th Ann. ACM Symposium on Theory of Computing, Kleinberg, J. M., Ed., New York: ACM, 2006, pp. 11-20.
    @incollection{ST:06, MRKEY = {2277126},
      AUTHOR = {Samorodnitsky, Alex and Trevisan, Luca},
      EDITOR = {Jon M. Kleinberg},
      TITLE = {Gowers uniformity, influence of variables, and {PCP}s},
      BOOKTITLE = {{P}roc. 38th {A}nn. {ACM} {S}ymposium on {T}heory of {C}omputing},
      PAGES = {11--20},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2006},
      DOI = {10.1145/1132516.1132519},
      MRCLASS = {68Q15},
      MRNUMBER = {2007h:68060},
      ISBN = {1-59593-134-1},
      }
  • [Sheppard:99] W. Sheppard, "On the application of the theory of error to cases of normal distribution and normal correlation," Phil. Trans. Royal Soc. London, vol. 192, pp. 101-168, 1899.
    @article{Sheppard:99, KEY = {Sh1899},
      AUTHOR = {W. Sheppard},
      TITLE = {On the application of the theory of error to cases of normal distribution and normal correlation},
      JOURNAL = {Phil. Trans. Royal Soc. London},
      FJOURNAL = {},
      VOLUME = {192},
      YEAR = {1899},
      PAGES = {101--168},
      }
  • [Szulga:98] J. Szulga, Introduction to random chaos, London: Chapman & Hall, 1998.
    @book{Szulga:98, MRKEY = {1681553},
      AUTHOR = {Szulga, Jerzy},
      TITLE = {Introduction to random chaos},
      PUBLISHER = {Chapman \& Hall},
      ADDRESS = {London},
      YEAR = {1998},
      PAGES = {viii+297},
      ISBN = {0-412-05091-9},
      MRCLASS = {60-02},
      MRNUMBER = {2000g:60003},
      ZBLNUMBER = {1053.37028},
      MRREVIEWER = {Pawel Hitczenko},
      }
  • [Talagrand:94] Go to document M. Talagrand, "On Russo’s approximate zero-one law," Annals Probab., vol. 22, iss. 3, pp. 1576-1587, 1994.
    @article{Talagrand:94, MRKEY = {1303654},
      AUTHOR = {Talagrand, Michel},
      TITLE = {On {R}usso's approximate zero-one law},
      JOURNAL = {Annals Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {22},
      YEAR = {1994},
      NUMBER = {3},
      PAGES = {1576--1587},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {28A35 (60K35)},
      MRNUMBER = {96g:28009},
      URL = {http://links.jstor.org/sici?sici=0091-1798(199407)22:3%3C1576:ORAZL%3E2.0.CO%3B2-S},
      ZBLNUMBER = {0819.28002},
      }
  • [Talagrand:96] Go to document M. Talagrand, "How much are increasing sets positively correlated?," Combinatorica, vol. 16, iss. 2, pp. 243-258, 1996.
    @article{Talagrand:96, MRKEY = {1401897},
      AUTHOR = {Talagrand, Michel},
      TITLE = {How much are increasing sets positively correlated?},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {16},
      YEAR = {1996},
      NUMBER = {2},
      PAGES = {243--258},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {05A20 (28A35)},
      MRNUMBER = {97e:05031},
      DOI = {10.1007/BF01844850},
      ZBLNUMBER = {0861.05008},
      MRREVIEWER = {Wen Li Chen},
      }
  • [Wolff:07] P. Wolff, "Hypercontractivity of simple random variables," Studia Math., vol. 180, iss. 3, pp. 219-236, 2007.
    @article{Wolff:07, MRKEY = {2314078},
      AUTHOR = {Wolff, Pawe{\l}},
      TITLE = {Hypercontractivity of simple random variables},
      JOURNAL = {Studia Math.},
      FJOURNAL = {Studia Mathematica},
      VOLUME = {180},
      YEAR = {2007},
      NUMBER = {3},
      PAGES = {219--236},
      ISSN = {0039-3223},
      MRCLASS = {60A10},
      MRNUMBER = {2008g:60009},
      ZBLNUMBER = {1133.60011},
      MRREVIEWER = {Ivan Gentil},
      }

Authors

Elchanan Mossel

University of California at Berkeley
Department of Statistics
367 Evans Hall
Berkeley, CA 94720-3860
United States

Ryan O’Donnell

Carnegie Mellon University
School of Computer Science
5000 Forbes Avenue
Pittsburgh, PA 15213-3891
United States

Krzysztof Oleszkiewicz

Faculty of Mathematics, Informatics and Mechanics
University of Warsaw
ul. Banacha 2
02-097 Warszawa
Poland