Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword

by Elchanan Mossel and Ryan O'Donnell

Theory of Computing, Volume 9(16), pp. 579-585, 2013

Bibliography with links to cited articles

[1]   Noga Alon, Irit Dinur, Ehud Friedgut, and Benjamin Sudakov: Graph products, Fourier analysis and spectral techniques. GAFA, 14(5):913–940, 2004. [doi:10.1007/s00039-004-0478-3]

[2]   Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. Preliminary version in FOCS’95. [doi:10.1109/18.556674]

[3]   Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In Proc. 49th FOCS, pp. 477–486. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.45]

[4]   Michael Ben-Or and Nathan Linial: Collective coin flipping, robust voting schemes and minima of Banzhaf values. In Proc. 26th FOCS, pp. 408–416. IEEE Comp. Soc. Press, 1985. [doi:10.1109/SFCS.1985.15]

[5]   Itai Benjamini, Gil Kalai, and Oded Schramm: Noise sensitivity of Boolean functions and applications to percolation. Publications Mathématiques de l’IHÉS, 90(1):5–43, 1999. [doi:10.1007/BF02698830]

[6]   Sergey G. Bobkov: An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space. Ann. Probab., 25(1):206–214, 1997. [doi:10.1214/aop/1024404285]

[7]   Aline Bonami: Étude des coefficients Fourier des fonctions de Lp(G). Annales de l’Institut Fourier, 20(2):335–402, 1970. [doi:10.5802/aif.357]

[8]   Jean Bourgain, Vitali Milman, and Haim Wolfson: On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986. [doi:10.1090/S0002-9947-1986-0819949-8]

[9]   Siu On Chan: Approximation resistance from pairwise independent subgroups. In Proc. 45th STOC, pp. 447–456. ACM Press, 2013. [doi:10.1145/2488608.2488665]

[10]   Anindya De, Elchanan Mossel, and Joe Neeman: Majority is stablest: discrete and SoS. In Proc. 45th STOC, pp. 477–486. ACM Press, 2013. Preprint available at arXiv. [doi:10.1145/2488608.2488668]

[11]   Ehud Friedgut: Sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12(4):1017–1054, 1999. [doi:10.1090/S0894-0347-99-00305-7]

[12]   Ehud Friedgut and Gil Kalai: Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124(10):2993–3002, 1996. [doi:10.1090/S0002-9939-96-03732-X]

[13]   Merrick L. Furst, Jeffrey Charles Jackson, and Sean W. Smith: Improved learning of AC0 functions. In Proc. 4th Ann. Conf. on Learning Theory (COLT’91), pp. 317–325, 1991. Available at author’s home page. [ACM:114866]

[14]   Christophe Garban, Gábor Pete, and Oded Schramm: The Fourier spectrum of critical percolation. Acta Mathematica, 205(1):19–104, 2010. [doi:10.1007/s11511-010-0051-x]

[15]   Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695–1708, 2009. Preliminary version in STOC’07. [doi:10.1137/070706550]

[16]   Oded Goldreich and Leonid A. Levin: A hard-core predicate for all one-way functions. In Proc. 21st STOC, pp. 25–32. ACM Press, 1989. [doi:10.1145/73007.73010]

[17]   Craig Gotsman and Nathan Linial: Spectral properties of threshold functions. Combinatorica, 14(1):35–50, 1994. [doi:10.1007/BF01305949]

[18]   Navin Goyal, Guy Kindler, and Michael E. Saks: Lower bounds for the noisy broadcast problem. SIAM J. Comput., 37(6):1806–1841, 2008. Preliminary version in FOCS’05. [doi:10.1137/060654864]

[19]   Ben Green: Finite field models in additive combinatorics. In Surveys in Combinatorics 2005, volume 327, pp. 1–27. Cambridge University Press, 2005. [doi:10.1017/CBO9780511734885.002, arXiv:math/0409420]

[20]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[21]   Hamed Hatami: A structure theorem for Boolean functions with small total influences. Ann. of Math., 176(1):509–533, 2012. [doi:10.4007/annals.2012.176.1.9, arXiv:1008.1021]

[22]   Robert B. Heckendorn and Alden H. Wright: Efficient linkage discovery by limited probing. Evolutionary Computation, 12(4):517–545, 2004. Preliminary version in GECCO’03. [doi:10.1162/1063656043138914]

[23]   Jeffrey Charles Jackson: The Harmonic Sieve: a novel application of Fourier analysis to machine learning theory and practice. Ph. D. thesis, Carnegie Mellon University, 1995. DTIC. [ACM:239947]

[24]   Jeff Kahn, Gil Kalai, and Nathan Linial: The influence of variables on Boolean functions. In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]

[25]   Gil Kalai: A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem. Advances in Applied Mathematics, 29(3):412–426, 2002. [doi:10.1016/S0196-8858(02)00023-4]

[26]   Gil Kalai and Nathan Linial: On the distance distribution of codes. IEEE Trans. Inform. Theory, 41(5):1467–1472, 1995. [doi:10.1109/18.412711]

[27]   Daniel M. Kane: A structure theorem for poorly anticoncentrated Gaussian chaoses and applications to the study of polynomial threshold functions. In Proc. 53rd FOCS, pp. 91–100. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.52]

[28]   Subhash Khot and Assaf Naor: Nonembeddability theorems via Fourier analysis. Mathematische Annalen, 334(4):821–852, 2006. Preliminary version in FOCS’05. [doi:10.1007/s00208-005-0745-0]

[29]   Eyal Kushilevitz and Yishay Mansour: Learning decision trees using the Fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993. Preliminary version in STOC’91. [doi:10.1137/0222080]

[30]   Nathan Linial, Yishay Mansour, and Noam Nisan: Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607–620, 1993. Preliminary version in FOCS’89. [doi:10.1145/174130.174138]

[31]   Yishay Mansour: Learning Boolean functions via the Fourier transform. In Vwani Roychowdhury, Kai-Yeung Siu, and Alon Orlitsky, editors, Theoretical Advances in Neural Computation and Learning, chapter 11, pp. 391–424. Kluwer/Springer, 1994. [doi:10.1007/978-1-4615-2696-4_11]

[32]   Rajeev Motwani, Assaf Naor, and Rina Panigrahy: Lower bounds on locality sensitive hashing. SIAM J. Discrete Math., 21(4):930–935, 2007. Preliminary version in SCG’06. [doi:10.1137/050646858]

[33]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. Preliminary version in STOC’90. [doi:10.1137/0222053]

[34]   Ryan O’Donnell: Hardness amplification within NP. J. Comput. System Sci., 69(1):68–94, 2004. Preliminary version in STOC’02. [doi:10.1016/j.jcss.2004.01.001]

[35]   Prasad Raghavendra: Approximating NP-hard problems: efficient algorithms and their limits. Ph. D. thesis, University of Washington, 2009. Berkeley. [ACM:1751149]

[36]   Tom Sanders: On the Bogolyubov-Ruzsa lemma. Anal. PDE, 5(3):627–655, 2012. [doi:10.2140/apde.2012.5.627]

[37]   Oded Schramm and Jeffrey E. Steif: Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math., 171(2):619–672, 2010. Also available among the Selected Works of Oded Schramm (Springer, 2011). [doi:10.4007/annals.2010.171.619]

[38]   Thomas Siegenthaler: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inform. Theory, 30(5):776–780, 1984. [doi:10.1109/TIT.1984.1056949]

[39]   Michel Talagrand: On Russo’s approximate zero-one law. Ann. Probab., 22(3):1576–1587, 1994. [doi:10.1214/aop/1176988612]

[40]   Michel Talagrand: How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996. [doi:10.1007/BF01844850]