@comment{Journal of the ACM}
@string{JACM="J. ACM"}

@comment{SIAM Journal on Computing}
@STRING{siamjc   = "SIAM J. Comput."}

@STRING{lncs     = "Lect. Notes in Comput. Sci."}
@STRING{comba    = "Combinatorica"}
@STRING{ipl      = "Inform. Process. Lett."}
@STRING{tcs      = "Theoret. Comput. Sci."}
@STRING{jcss     = "J. Comput. System Sci."}
@STRING{jams     = "J. Amer. Math. Soc."}
@STRING{ccomplex = "Comput. Complexity"}
@STRING{tams     = "Trans. Amer. Math. Soc."}
@STRING{oup      = "Oxford University Press"}
@STRING{cup      = "Cambridge University Press"}
@STRING{ams      = "American Mathematical Society"}
@STRING{springer = "Springer"}

@comment{Annals of Mathematics.}
@string{AnnofMath="Ann. of Math."}

@comment{Israel Journal of Mathematics}
@string{IsraelJMath="Israel J. Math."}

@comment{Proceedings of the American Mathematical Society}
@string{ProcAmerMathSoc="Proc. Amer. Math. Soc."}

@comment{Advances in Applied Mathematics}
@string{AdvinApplMath="Adv. in Appl. Math."}

@comment{Combinatorics, Probability and Computing}
@string{CombinProbabComput="Combin. Probab. Comput."}

@comment{American Journal of Mathematics}
@string{AmerJMath="Amer. J. Math."}

@comment{Geometric and Functional Analysis}
@string{GeomFunctAnal="Geom. Funct. Anal."}

@comment{The Annals of Probability}
@string{AnnProbab="Ann. Probab."}

@INPROCEEDINGS{aak:testingkwise,
AUTHOR    = "N. Alon and A. Andoni and T. Kaufman and K. Matulef and R. Rubinfeld and N. Xie",
TITLE     = "Testing k-wise and almost k-wise independence",
BOOKTITLE = "Proc. 39th STOC",
PUBLISHER = "ACM Press",
PAGES     = "496--505",
YEAR      = 2007,
eprint="stoc:1250790.1250863"
}

@ARTICLE{ambainis:aa,
AUTHOR    = "A. Ambainis",
TITLE     = "A note on quantum black-box complexity of almost all {B}oolean functions",
JOURNAL   = ipl,
VOLUME    = 71,
NUMBER    = 1,
PAGES     = "5--7",
YEAR      = 1999,
eprint="ipl:10.1016/S0020-0190(99)00079-4"
}

@ARTICLE{almss:pcp,        
AUTHOR    = "S. Arora and C. Lund and R. Motwani and M. Sudan and M. Szegedy",
TITLE     = "Proof Verification and the Hardness of Approximation Problems",
JOURNAL   = jacm,
VOLUME    = 45,
NUMBER    = 3,
PAGES     = "501--555",
YEAR      = 1998,
NOTE      = "Earlier version in FOCS'92",
eprint="jacm:278298.278306"
}

@BOOK{arora&barak:cc,  
AUTHOR    = "S. Arora and B. Barak",
TITLE     = "Complexity Theory: A Modern Approach",
PUBLISHER = cup,
YEAR      = 2009,
NOTE      = "To appear. Preliminary version available at \url{http://www.cs.princeton.edu/theory/complexity}",
}

@ARTICLE{arrow:difficulty,      
AUTHOR    = "K. Arrow",
TITLE     = "A difficulty in the concept of social welfare",
JOURNAL   = "J. Political Economy",
VOLUME    = 58,
NUMBER    = 4,
PAGES     = "328--346",
YEAR      = 1950,
doi="10.1086/256963"
}

@ARTICLE{Bec75,
 AUTHOR =       "W. Beckner",
 TITLE =        "Inequalities in {F}ourier Analysis",
 JOURNAL =      AnnofMath,
 YEAR =         "1975",
 volume =       "102",
 pages =        "159--182",
}

@INCOLLECTION{benor&linial:coinflippingj,
AUTHOR    = "M. {Ben-Or} and N. Linial",
TITLE     = "Collective Coin Flipping",
BOOKTITLE = "Randomness and Computation",
EDITOR    = "S. Micali",
PAGES     = "91--115",
YEAR      = 1989,
PUBLISHER = "JAI Press",
NOTE      = "Earlier version in FOCS'85",
}

@TECHREPORT{bcs:fourier,
AUTHOR    = "A. Bernasconi and B. Codenotti and J. Simon",
TITLE     = "On the {Fourier} Analysis of {Boolean} Functions",
INSTITUTION = "Istituto di Matematica Computazionale, Pisa",
NUMBER    = "IMC B4-97-03",
YEAR      = 1997,
}

@ARTICLE{Bon70,
 AUTHOR =       "A. Bonami",
 TITLE  =       "{\'E}tude des coefficients de {Fourier} des fonctions de {$L^p(G)$}",
 JOURNAL =      "Annales de l'Institut Fourier",
 volume =       "20",
 number  =      "2",
 pages =        "335--402",
 year   =       "1970",
}

@ARTICLE{bourgain:fourierdistribution,
AUTHOR    = "J. Bourgain",
TITLE     = "On the distribution of the {F}ourier spectrum of {B}oolean functions",
JOURNAL   = IsraelJMath,
VOLUME    = 131,
NUMBER    = 1,
PAGES     = "269--276",
YEAR      = 2002,
eprint="springer:657221r06x818652"
}

@ARTICLE{bkkkl:influence,
AUTHOR    = "J. Bourgain and J. Kahn and G. Kalai and G. Katznelson and N. Linial",
TITLE     = "The Influence of Variables in Product Spaces",
JOURNAL   = IsraelJMath,
VOLUME    = 77,
number="1--2",
PAGES     = "55--64",
YEAR      = 1992,
eprint="springer:456880489w184683"
}

@ARTICLE{bmos:dnfrandomwalkj,
AUTHOR    = "N. Bshouty and E. Mossel and R. {O'Donnell} and R. Servedio",
TITLE     = "Learning {DNF} from Random Walks",
JOURNAL   = jcss,
VOLUME    = 71,
NUMBER    = 3,
PAGES     = "250--265",
YEAR      = 2005,
NOTE      = "Earlier version in FOCS'03",
eprint="jcss:10.1016/j.jcss.2004.10.010"
}

@ARTICLE{buhrman&wolf:dectreesurvey,
AUTHOR    = "H. Buhrman and Wolf, R. {de}",
TITLE     = "Complexity Measures and Decision Tree Complexity: A Survey",
JOURNAL   = tcs,
VOLUME    = 288,
NUMBER    = 1,
PAGES     = "21--43",
YEAR      = 2002,
eprint="tcs:10.1016/S0304-3975(01)00144-X"
}

@INPROCEEDINGS{bvw:smallbias,
AUTHOR    = "H. Buhrman and N. Vereshchagin and Wolf, R. {de}",
TITLE     = "On computation and communication with small bias",
BOOKTITLE = "Proc. 22nd Conference on Comput. Complexity",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "24--32",
YEAR      = 2007,
eprint="ccc:10.1109/CCC.2007.18"
}

@INPROCEEDINGS{brw:hypercontractive,
AUTHOR    = "A. {Ben-Aroya} and O. Regev and Wolf, R. {de}",
TITLE     = "A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing",
BOOKTITLE = "Proc. 49th FOCS",
PUBLISHER = "IEEE Computer Society Press",
YEAR      = 2008,
}

@INPROCEEDINGS{ckkrs:cut,    
AUTHOR    = "S. Chawla and R. Krauthgamer and R. Kumar and Y. Rabani and D. Sivakumar",
TITLE     = "On the hardness of approximating sparsest cut and multicut",
BOOKTITLE = "Proc. 20th Conf. Comput. Complexity",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "144--153",
YEAR      = 2005,
eprint="ccc:10.1109/CCC.2005.20"
}

@ARTICLE{dinur:pcp,        
AUTHOR    = "I. Dinur",
TITLE     = "The {PCP} theorem by gap amplification",
JOURNAL   = jacm,
VOLUME    = 54,
NUMBER    = "3",
pages="12",
YEAR      = 2007,
NOTE      = "Earlier version in STOC'06",
eprint="jacm:10.1145/1236457.1236459"
}

@ARTICLE{dfko:fouriertails,
AUTHOR    = "I. Dinur and E. Friedgut and G. Kindler and R. {O'Donnell}",
TITLE     = "On the {F}ourier tails of bounded functions over the discrete cube",
JOURNAL   = IsraelJMath,
VOLUME    = 160,
NUMBER    = 1,
PAGES     = "389--412",
YEAR      = 2007,
NOTE      = "Earlier version in STOC'06",
eprint="springer:43k0r5p3g28k508g,stoc:10.1145/1132516.1132580"
}

@INPROCEEDINGS{dmr:coloring,
AUTHOR    = "I. Dinur and E. Mossel and O. Regev",
TITLE     = "Conditional hardness for approximate coloring",
BOOKTITLE = "Proc. 38nd STOC",
PUBLISHER = "ACM Press",
PAGES     = "344--353",
YEAR      = 2006,
eprint="stoc:1132516.1132567"
}

@ARTICLE{erdos&renyi:randomgraphs,  
AUTHOR    = "P. Erd{\H{o}}s and A. R{\'e}nyi",
TITLE     = "On random graphs {I}",
JOURNAL   = "Publicationes Mathematicae",
VOLUME    = 6,
PAGES     = "290--297",
YEAR      = 1959,
}

@ARTICLE{friedgut:fewcoor,  
AUTHOR    = "E. Friedgut",
TITLE     = "{Boolean} functions with low average sensitivity depend on few coordinates",
JOURNAL   = comba,
VOLUME    = 18,
NUMBER    = 1,
PAGES     = "27--35",
YEAR      = 1998,
eprint="springer:fxcj48rnbwv5gjdb"
}

@ARTICLE{friedgut&kalai:sharp,   
AUTHOR    = "E. Friedgut and G. Kalai",
TITLE     = "Every monotone graph property has a sharp threshold",
JOURNAL   = ProcAmerMathSoc,
VOLUME    = 124,
PAGES     = "2993--3002",
YEAR      = 1996,
www="http://www.ams.org/proc/1996-124-10/S0002-9939-96-03732-X/home.html"
}

@ARTICLE{fkn:firsttwolevels,     
AUTHOR    = "E. Friedgut and G. Kalai and A. Naor",
TITLE     = "{Boolean} functions whose {Fourier} transform is concentrated at the first two levels",
JOURNAL   = AdvinApplMath,
VOLUME    = 29,
NUMBER    = 3,
PAGES     = "427--437",
YEAR      = 2002,
eprint="elsevier:10.1016/S0196-8858(02)00024-6"
}

@ARTICLE{friedgut:bkkkl,
AUTHOR    = "E. Friedgut",
TITLE     = "Influences in product spaces: {KKL} and {BKKKL} revisited",
JOURNAL   = CombinProbabComput,
VOLUME    = 13,
number=1,
PAGES     = "17--29",
YEAR      = 2004,
eprint="cambridge:10.1017/S0963548303005832"
}

@INPROCEEDINGS{fkn:elections,
AUTHOR    = "E. Friedgut and G. Kalai and N. Nisan",
TITLE     = "Elections Can be Manipulated Often",
BOOKTITLE = "Proc. 49th FOCS",
PUBLISHER = "IEEE Computer Society Press",
YEAR      = 2008,
}

@ARTICLE{fkrss:juntas,
AUTHOR    = "E. Fischer and G. Kindler and D. Ron and S. Safra and A. Samorodnitsky",
TITLE     = "Testing juntas",
JOURNAL   = jcss,
VOLUME    = 68,
NUMBER    = 4,
PAGES     = "753--787",
YEAR      = 2004,
NOTE      = "Earlier version in FOCS'02",
eprint="jcss:10.1016/j.jcss.2003.11.004"
}

@INPROCEEDINGS{gkkrw:1way,
AUTHOR    = "D. Gavinsky and J. Kempe and I. Kerenidis and R. Raz and Wolf, R. {de}",
TITLE     = "Exponential separations for one-way quantum communication complexity, with applications to cryptography",
BOOKTITLE = "Proc. 39th STOC",
PUBLISHER = "ACM Press",
PAGES     = "516--525",
YEAR      = 2007,
eprint="stoc:1250790.1250866"
}

@INPROCEEDINGS{goldreich&levin,
AUTHOR    = "O. Goldreich and L. Levin",
TITLE     = "A Hard-Core Predicate for all One-Way Functions",
BOOKTITLE = "Proc. 21st STOC",
PUBLISHER = "ACM Press",
PAGES     = "25--32",
YEAR      = 1989,
eprint="stoc:73007.73010"
}

@ARTICLE{Gross75,
    AUTHOR = {Gross, L.},
     TITLE = {Logarithmic {S}obolev inequalities},
   JOURNAL = AmerJMath,
  FJOURNAL = {American Journal of Mathematics},
    VOLUME = {97},
      YEAR = {1975},
    NUMBER = {4},
     PAGES = {1061--1083},
}

@BOOK{guruswami:alglistdecoding,
AUTHOR    = "V. Guruswami",
TITLE     = "Algorithmic Results in List Decoding",
SERIES    = "Foundations and Trends in Theoretical Computer Science", 
VOLUME    = "2(2)",
PUBLISHER = "Now Publishers",
YEAR      = 2007,
}

@ARTICLE{hastad:optimalj,
AUTHOR    = "J. H{\aa}stad",
TITLE     = "Some Optimal Inapproximability Results",
JOURNAL   = jacm,
VOLUME    = 48,
NUMBER    = 4,
PAGES     = "798--859",
YEAR      = 2001,
NOTE      = "Earlier version in STOC'97",
eprint="jacm:10.1145/502090.502098"
}

@ARTICLE{jackson:dnf,
AUTHOR    = "J. Jackson",
TITLE     = "An Efficient Membership-Query Algorithm for Learning {DNF} with Respect to the Uniform Distribution",
JOURNAL   = jcss,
VOLUME    = 55,
NUMBER    = 3,
PAGES     = "414--440",
YEAR      = 1997,
NOTE      = "Earlier version in FOCS'94",
eprint="jcss:10.1006/jcss.1997.1533"
}

@BOOK{janson:gaussian,     
AUTHOR    = "S. Janson",
TITLE     = "Gaussian Hilbert Spaces",
SERIES    = "Cambridge Tracts in Mathematics",
VOLUME    = 129,
PUBLISHER = cup,
YEAR      = 1997,
}

@INPROCEEDINGS{kkl:influence,
AUTHOR    = "J. Kahn and G. Kalai and N. Linial",
TITLE     = "The Influence of Variables on {B}oolean Functions",
BOOKTITLE = "Proc. 29th FOCS",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "68--80",
YEAR      = 1988,
}

@TECHREPORT{kalai:socialchoice,   
AUTHOR    = "G. Kalai",
TITLE     = "Noise sensitivity and chaos in social choice theory",
INSTITUTION = "Discussion Paper Series dp399. Center for rationality and interactive decision theory, Hebrew University",
YEAR      = 2005,
NOTE      = "Available at \url{http://www.ma.huji.ac.il/~kalai/CHAOS.pdf}",
}

@INCOLLECTION{kalai&safra:threshold,
AUTHOR    = "G. Kalai and S. Safra",
TITLE     = "Threshold Phenomena and Influence",
PAGES     = "25--60",
CROSSREF  = "ccandphysics",
}

@BOOK{ccandphysics,
EDITOR    = "A.G. Percus and G. Istrate and C. Moore",
TITLE     = "Computational Complexity and Statistical Physics",
BOOKTITLE = "Computational Complexity and Statistical Physics",
PUBLISHER = oup,
YEAR      = "2006",
}

@INPROCEEDINGS{khot:ugc,       
AUTHOR    = "S. Khot",
TITLE     = "On the power of unique 2-Prover 1-Round games",
BOOKTITLE = "Proc. 34th STOC",
PUBLISHER = "ACM Press",
PAGES     = "767-–775",
YEAR      = 2002,
eprint="stoc:509907.510017"
}

@ARTICLE{kkmo:maxcutj,    
AUTHOR    = "S. Khot and G. Kindler and E. Mossel and R. {O'Donnell}",
TITLE     = "Optimal inapproximability results for {MAX-CUT} and other 2-variable {CSP}s?",
JOURNAL   = siamjc,
VOLUME    = 37,
NUMBER    = 1,
PAGES     = "319--357",
YEAR      = 2007,
eprint="sicomp:10.1137/S0097539705447372"
}

@INPROCEEDINGS{khot&vishnoi:cutproblems,
AUTHOR    = "S. Khot and N. Vishnoi",
TITLE     = "The unique games conjecture, integrality gap for cut problems and
embeddability of negative type metrics into {$\ell_1$}",
BOOKTITLE = "Proc. 46th FOCS",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "53--62",
YEAR      = 2005,
eprint="focs:10.1109/SFCS.2005.74"
}

@INPROCEEDINGS{khot&odonnell:maxcutgain,
AUTHOR    = "S. Khot and R. {O'Donnell}",
TITLE     = "{SDP} gaps and {UGC}-hardness for {MAXCUTGAIN}",
BOOKTITLE = "Proc. 47th FOCS",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "217--226",
YEAR      = 2006,
eprint="focs:10.1109/FOCS.2006.67"
}

@ARTICLE{khot&regev:vertexcover,
AUTHOR    = "S. Khot and O. Regev",
TITLE     = "Vertex Cover Might be Hard to Approximate to within {$2-\epsilon$}",
JOURNAL   = jcss,
VOLUME    = 74,
NUMBER    = 3,
PAGES     = "335--349",
YEAR      = 2008,
NOTE      = "Earlier version in Complexity'03",
eprint="jcss:10.1016/j.jcss.2007.06.019"
}

@ARTICLE{klauck:qcclowerj,
AUTHOR    = "H. Klauck",
TITLE     = "Lower bounds for quantum communication complexity",
JOURNAL   = siamjc,
VOLUME    = 37,
NUMBER    = 1,
PAGES     = "20--46",
YEAR      = 2007,
NOTE      = "Earlier version in FOCS'01",
eprint="sicomp:10.1137/S0097539702405620"
}

@ARTICLE{klivans&servedio:dnf,
AUTHOR    = "A. Klivans and R. Servedio",
TITLE     = "Learning {DNF} in time {$2^{\tilde{O}(n^{1/3})}$}",
JOURNAL   = jcss,
VOLUME    = 68,
NUMBER    = 2,
PAGES     = "303--318",
YEAR      = 2004,
NOTE      = "Earlier version in STOC'01",
eprint="jcss:10.1016/j.jcss.2003.07.007"
}

@ARTICLE{kushilevitz&mansour:dectrees,
AUTHOR    = "E. Kushilevitz and Y. Mansour",
TITLE     = "Learning Decision Trees Using the {F}ourier Spectrum",
JOURNAL   = siamjc,
VOLUME    = 22,
NUMBER    = 6,
PAGES     = "1331--1348",
YEAR      = 1993,
NOTE      = "Earlier version in STOC'91",
eprint="sicomp:10.1137/0222080"
}

@ARTICLE{LeeNaor04,
   AUTHOR = {Lee, J. R. and Naor, A.},
    TITLE = {Embedding the diamond graph in {$L\sb p$} and dimension
             reduction in {$L\sb 1$}},
  JOURNAL = GeomFunctAnal,
   VOLUME = {14},
     YEAR = {2004},
   NUMBER = {4},
    PAGES = {745--747},
eprint="springer:r36q4553fwheur9u"
}

@ARTICLE{lmn:learnability,
AUTHOR    = "N. Linial and Y. Mansour and N. Nisan",
TITLE     = "Constant Depth Circuits, {F}ourier Transform, and Learnability",
JOURNAL   = jacm,
VOLUME    = 40,
NUMBER    = 3,
PAGES     = "607--620",
YEAR      = 1993,
NOTE      = "Earlier version in FOCS'89",
eprint="jacm:10.1145/502090.502098"
}

@BOOK{MacWilliamsS77,
AUTHOR    = "F. MacWilliams and N. Sloane",
TITLE     = "The Theory of Error-Correcting Codes",
PUBLISHER = "North-Holland",
YEAR      = 1977,
}

@ARTICLE{mansour:dnfuniform,
AUTHOR    = "Y. Mansour",
TITLE     = "An {$O(n^{\log\log n})$} learning algorithm for {DNF} under the uniform distribution",
JOURNAL   = jcss,
VOLUME    = 50,
NUMBER    = 3,
PAGES     = "543--550",
YEAR      = 1995,
NOTE      = "Earlier version in COLT'92",
eprint="jcss:10.1006/jcss.1995.1043"
}

@ARTICLE{mos:learningjuntas,
AUTHOR    = "E. Mossel and R. {O'Donnell} and R. Servedio",
TITLE     = "Learning functions of {$k$} relevant variables",
JOURNAL   = jcss,
VOLUME    = 69,
NUMBER    = 3,
PAGES     = "421--434",
YEAR      = 2004,
NOTE      = "Earlier version in STOC'03",
eprint="jcss:10.1016/j.jcss.2004.04.002"
}

@ARTICLE{moo:noisestability,
AUTHOR    = "E. Mossel and R. {O'Donnell} and K. Oleszkiewicz",
TITLE     = "Noise stability of functions with low influences: invariance and optimality",
JOURNAL   = AnnofMath,
YEAR      = 2008,
NOTE      = "To appear. Earlier version in FOCS'05",
}

@INPROCEEDINGS{navon&samorodnitsky:delsarte,    
AUTHOR    = "M. Navon and A. Samorodnitsky",
TITLE     = "On {D}elsarte's Linear Programming Bounds for Binary Codes",
BOOKTITLE = "Proc. 46th FOCS",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "327--338",
YEAR      = 2005,
eprint="focs:10.1109/SFCS.2005.55"
}

@ARTICLE{nisan&szegedy:degree,
AUTHOR    = "N. Nisan and M. Szegedy",
TITLE     = "On the Degree of {B}oolean functions as Real Polynomials",
JOURNAL   = ccomplex,
VOLUME    = 4,
NUMBER    = 4,
PAGES     = "301--313",
YEAR      = 1994,
NOTE      = "Earlier version in STOC'92",
eprint="cc:p1711275700w5264"
}

@MISC{odonnell:notes,
AUTHOR    = "R. {O'Donnell}",
TITLE     = {Lecture notes for a course ``{Analysis} of {Boolean} functions''},
NOTE      = "Available at \url{http://www.cs.cmu.edu/~odonnell/boolean-analysis}",
YEAR      = 2007,
}

@TECHREPORT{odonnell:survey,    
AUTHOR    = "R. {O'Donnell}",
TITLE     = "Some Topics in Analysis of {Boolean} Functions",
INSTITUTION = "ECCC Report TR08--055",
YEAR      = 2008,
NOTE      = "Paper for an invited talk at STOC'08",
eprint="eccc:TR08-055"
}

@INPROCEEDINGS{odonnell&servedio:extremal,
AUTHOR    = "R. {O'Donnell} and R. Servedio",
TITLE     = "Extremal properties of polynomial threshold functions",
BOOKTITLE = "Proc. 18th Conf. Comput. Complexity",
PUBLISHER = "IEEE Computer Society Press",
YEAR      = 2003,
PAGES     = "3--12",
}

@ARTICLE{odonnell&servedio:montrees,
AUTHOR    = "R. {O'Donnell} and R. Servedio",
TITLE     = "Learning Monotone Decision Trees in Polynomial Time",
JOURNAL   = siamjc,
VOLUME    = 37,
NUMBER    = 3,
PAGES     = "827--844",
YEAR      = 2007,
NOTE      = "Earlier version in Complexity'06",
eprint="sicomp:10.1137/060669309"
}

@INPROCEEDINGS{dsss:dectreeinfluence,
AUTHOR    = "R. {O'Donnell} and M. Saks and O. Schramm and R. Servedio",
TITLE     = "Every decision tree has an influential variable",
BOOKTITLE = "Proc. 46th FOCS",
PUBLISHER = "IEEE Computer Society Press",
PAGES     = "31--39",
YEAR      = 2005,
eprint="focs:10.1109/SFCS.2005.34"
}

@INPROCEEDINGS{raghavendra:csp,
AUTHOR    = "P. Raghavendra",
TITLE     = "Optimal algorithms and inapproximability results for every {CSP}?",
BOOKTITLE = "Proc. 40th STOC",
PUBLISHER = "ACM Press",
PAGES     = "245--254",
YEAR      = 2008,
eprint="stoc:1374376.1374414"
}

@ARTICLE{raz:ccfourier,
AUTHOR    = "R. Raz",
TITLE     = "{Fourier} Analysis for Probabilistic Communication Complexity",
JOURNAL   = ccomplex,
VOLUME    = 5,
NUMBER    = "3/4",
PAGES     = "205--221",
YEAR      = "1995",
eprint="cc:p7346675080r85r4"
}

@MASTERSTHESIS{stefankovic:thesis,
AUTHOR    = "D. {\v{S}}tefankovi{\v{c}}",
TITLE     = "{Fourier} transforms in computer science",
SCHOOL    = "University of Chicago, Department of Computer Science",
YEAR      = 2000,
NOTE      = "Available at \url{http://www.cs.rochester.edu/~stefanko/Publications/Fourier.ps}",
}

@ARTICLE{schwartz:probabilistic,
AUTHOR    = "J. T. Schwartz",
TITLE     = "Fast probabilistic algorithms for verification of polynomial identities",
JOURNAL   = jacm,
VOLUME    = 27,
number=4,
PAGES     = "701--717",
YEAR      = 1980,
eprint="jacm:10.1145/322217.322225"
}

@ARTICLE{servedio:lowweightj,
AUTHOR    = "R. Servedio",
TITLE     = "Every linear threshold function has a low-weight approximator",
JOURNAL   = ccomplex,
VOLUME    = 16,
NUMBER    = 2,
YEAR      = 2007,
PAGES     = "180--209",
NOTE      = "Earlier version in Complexity'06",
eprint="cc:64682257x6344776"
}

@TECHREPORT{sherstov:dualpoly,    
AUTHOR    = "A. Sherstov",
TITLE     = "Communication Lower Bounds Using Dual Polynomials",
INSTITUTION = "ECCC Report TR08--057",
YEAR      = 2008,
eprint="eccc:TR08-057"
}

@ARTICLE{shi:lowerbound,
AUTHOR    = "Y. Shi",
TITLE     = "Lower bounds of quantum black-box complexity and degree of approximating
             polynomials by influence of {B}oolean variables",
JOURNAL   = ipl,
VOLUME    = 75,
NUMBER    = "1--2",
PAGES     = "79--83",
YEAR      = 2000,
eprint="ipl:10.1016/S0020-0190(00)00069-7"
}

@INPROCEEDINGS{sudan:listdecodingsurvey,
AUTHOR    = "M. Sudan",
TITLE     = "List decoding: Algorithms and applications",
BOOKTITLE = "Proc. Intern. Conf. IFIP TCS",
SERIES    = lncs,
VOLUME    = 1872,
PUBLISHER = springer,
PAGES     = "25--41",
YEAR      = 2000,
}

@ARTICLE{talagrand:increasingsets,
AUTHOR    = "M. Talagrand",
TITLE     = "How much are increasing sets positively correlated?",
JOURNAL   = comba,
VOLUME    = 16,
NUMBER    = 2,
PAGES     = "243--258",
YEAR      = 1996,
eprint="springer:uvm737238p44xk37"
}

@ARTICLE{talagrand:russo, 
AUTHOR    = "M. Talagrand",
TITLE     = "On {R}usso's approximate 0-1 law",
JOURNAL   = AnnProbab,
VOLUME    = 22,
number=3,
PAGES     = "1576--1587",
YEAR      = 1994,
note="\url{http://projecteuclid.org/euclid.aop/1176988612}"
}

@INPROCEEDINGS{zippel:probabilistic,
AUTHOR    = "R. E. Zippel",
TITLE     = "Probabilistic algorithms for sparse polynomials",
BOOKTITLE = "Proc. EUROSAM 79",
SERIES    = lncs,
PUBLISHER = springer,
VOLUME    = 72,
PAGES     = "216--226",
YEAR      = 1979,
}