Special issue on analysis of Boolean functions: guest editors’ foreword. (English) Zbl 1298.00169
From the text: Over the last decade, a number of powerful themes have emerged in the analysis of Boolean functions: the dichotomy between “juntas” and functions with small influences; noise sensitivity/stability; the “small-set expansion” of the Boolean cube; the role of Gaussian analysis/geometry; probabilistic invariance principles; and regularity lemmas. This deepening understanding of the field has led to quite a few exciting developments in the last five years.
MSC:
| 00B15 | Collections of articles of miscellaneous specific interest |
| 06-06 | Proceedings, conferences, collections, etc. pertaining to ordered structures |
| 68-06 | Proceedings, conferences, collections, etc. pertaining to computer science |
| 06E30 | Boolean functions |
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
Keywords:
Boolean functionsReferences:
| [1] | [1] NOGAALON, IRITDINUR, EHUDFRIEDGUT,ANDBENJAMINSUDAKOV: Graph products, Fourier analysis and spectral techniques. GAFA, 14(5):913–940, 2004. [doi:10.1007/s00039-0040478-3]579 |
| [2] | [2] MIHIRBELLARE, DONCOPPERSMITH, JOHANHÅSTAD, MARCOSA. KIWI,ANDMADHU SUDAN: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. Preliminary version inFOCS’95. [doi:10.1109/18.556674]579,581 |
| [3] | [3] AVRAHAMBEN-AROYA, ODEDREGEV,ANDRONALD DEWOLF: 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]579 |
| [4] | [4] MICHAELBEN-OR ANDNATHANLINIAL: 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]579,581 |
| [5] | [5] ITAIBENJAMINI, GILKALAI,ANDODEDSCHRAMM: 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]581 |
| [6] | [6] SERGEYG. 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]579 |
| [7] | [7] ALINEBONAMI: Étude des coefficients Fourier des fonctions de Lp(G). Annales de l’Institut Fourier, 20(2):335–402, 1970. [doi:10.5802/aif.357]581 |
| [8] | [8] JEANBOURGAIN, VITALIMILMAN,ANDHAIMWOLFSON: On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986. [doi:10.1090/S0002-9947-1986-0819949-8]579 |
| [9] | [9] SIUONCHAN: Approximation resistance from pairwise independent subgroups. In Proc. 45th STOC, pp. 447–456. ACM Press, 2013. [doi:10.1145/2488608.2488665]579 |
| [10] | [10] ANINDYADE, ELCHANANMOSSEL,ANDJOENEEMAN: Majority is stablest: discrete and SoS.In Proc. 45th STOC, pp. 477–486. ACM Press, 2013.Preprint available atarXiv. [doi:10.1145/2488608.2488668]579 |
| [11] | [11] EHUDFRIEDGUT: 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]579,581 |
| [12] | [12] EHUDFRIEDGUT ANDGILKALAI: 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]581 · Zbl 0864.05078 |
| [13] | [13] MERRICKL. FURST, JEFFREYCHARLESJACKSON,ANDSEANW. SMITH: Improved learning of AC0functions. In Proc. 4th Ann. Conf. on Learning Theory (COLT’91), pp. 317–325, 1991. Available atauthor’s home page. [ACM:114866]581 THEORY OFCOMPUTING, Volume 9 (2013), pp. 579–585582 FOREWORD TOSPECIALISSUE ONANALYSIS OFBOOLEANFUNCTIONS |
| [14] | [14] CHRISTOPHEGARBAN, GÁBORPETE,ANDODEDSCHRAMM: The Fourier spectrum of critical percolation. Acta Mathematica, 205(1):19–104, 2010. [doi:10.1007/s11511-010-0051-x]580 |
| [15] | [15] DMITRYGAVINSKY, JULIAKEMPE, IORDANISKERENIDIS, RANRAZ,ANDRONALD DE WOLF: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695–1708, 2009. Preliminary version inSTOC’07. [doi:10.1137/070706550]579 |
| [16] | [16] ODEDGOLDREICH ANDLEONIDA. 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]581 |
| [17] | [17] CRAIGGOTSMAN ANDNATHANLINIAL: Spectral properties of threshold functions. Combinatorica, 14(1):35–50, 1994. [doi:10.1007/BF01305949]581 |
| [18] | [18] NAVINGOYAL, GUYKINDLER,ANDMICHAELE. SAKS: Lower bounds for the noisy broadcast problem. SIAM J. Comput., 37(6):1806–1841, 2008. Preliminary version inFOCS’05. [doi:10.1137/060654864]579 |
| [19] | [19] BENGREEN: 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]579 |
| [20] | [20] JOHANHÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version inSTOC’97. [doi:10.1145/502090.502098]579,581 |
| [21] | [21] HAMEDHATAMI: 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]580 · Zbl 1253.05128 |
| [22] | [22] ROBERTB. HECKENDORN ANDALDENH. WRIGHT: Efficient linkage discovery by limited probing. Evolutionary Computation, 12(4):517–545, 2004. Preliminary version inGECCO’03. [doi:10.1162/1063656043138914]579 |
| [23] | [23] JEFFREYCHARLESJACKSON: 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]581 |
| [24] | [24] JEFFKAHN, GILKALAI,ANDNATHANLINIAL: 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] 579,581 |
| [25] | [25] GILKALAI: 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] 579 |
| [26] | [26] GILKALAI ANDNATHANLINIAL: On the distance distribution of codes. IEEE Trans. Inform. Theory, 41(5):1467–1472, 1995. [doi:10.1109/18.412711]579 THEORY OFCOMPUTING, Volume 9 (2013), pp. 579–585583 ELCHANANMOSSEL ANDRYANO’DONNELL |
| [27] | [27] DANIELM. 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]580 |
| [28] | [28] SUBHASHKHOT ANDASSAFNAOR: Nonembeddability theorems via Fourier analysis. Mathematische Annalen, 334(4):821–852, 2006. Preliminary version inFOCS’05. [doi:10.1007/s00208-0050745-0]579 |
| [29] | [29] EYALKUSHILEVITZ ANDYISHAYMANSOUR: Learning decision trees using the Fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993. Preliminary version inSTOC’91. [doi:10.1137/0222080] 581 |
| [30] | [30] NATHANLINIAL, YISHAYMANSOUR,ANDNOAMNISAN: Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607–620, 1993. Preliminary version inFOCS’89. [doi:10.1145/174130.174138]579,581 |
| [31] | [31] YISHAYMANSOUR: Learning Boolean functions via the Fourier transform. In VWANIROYCHOWDHURY, KAI-YEUNGSIU,ANDALONORLITSKY, editors, Theoretical Advances in Neural Computation and Learning, chapter 11, pp. 391–424. Kluwer/Springer, 1994. [doi:10.1007/978-14615-2696-4_11]579 · Zbl 0845.68093 |
| [32] | [32] RAJEEVMOTWANI, ASSAFNAOR,ANDRINAPANIGRAHY: Lower bounds on locality sensitive hashing. SIAM J. Discrete Math., 21(4):930–935, 2007. Preliminary version inSCG’06. [doi:10.1137/050646858]579 |
| [33] | [33] JOSEPHNAOR ANDMONINAOR: Small-bias probability spaces: Efficient constructions and applications.SIAM J. Comput., 22(4):838–856, 1993.Preliminary version inSTOC’90. [doi:10.1137/0222053]579 |
| [34] | [34] RYANO’DONNELL: Hardness amplification within NP. J. Comput. System Sci., 69(1):68–94, 2004. Preliminary version inSTOC’02. [doi:10.1016/j.jcss.2004.01.001]579 |
| [35] | [35] PRASADRAGHAVENDRA: Approximating NP-hard problems: efficient algorithms and their limits. Ph. D. thesis, University of Washington, 2009.Berkeley. [ACM:1751149]579 |
| [36] | [36] TOMSANDERS:On the Bogolyubov-Ruzsa lemma.Anal. PDE, 5(3):627–655, 2012. [doi:10.2140/apde.2012.5.627]580 · Zbl 1320.11009 |
| [37] | [37] ODEDSCHRAMM ANDJEFFREYE. STEIF: Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math., 171(2):619–672, 2010. Also available among theSelected Works of Oded Schramm (Springer, 2011). [doi:10.4007/annals.2010.171.619]579 |
| [38] | [38] THOMASSIEGENTHALER:Correlation-immunityofnonlinearcombiningfunctions for cryptographic applications.IEEE Trans. Inform. Theory,30(5):776–780,1984. [doi:10.1109/TIT.1984.1056949]579 THEORY OFCOMPUTING, Volume 9 (2013), pp. 579–585584 FOREWORD TOSPECIALISSUE ONANALYSIS OFBOOLEANFUNCTIONS |
| [39] | [39] MICHELTALAGRAND: On Russo’s approximate zero-one law. Ann. Probab., 22(3):1576–1587, 1994. [doi:10.1214/aop/1176988612]581 |
| [40] | [40] MICHELTALAGRAND: How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996. [doi:10.1007/BF01844850]581 GUEST EDITORS Elchanan Mossel U.C. Berkeley, CA, USA mosselstat berkeley edu www.stat.berkeley.edu/ mossel/ Ryan O’Donnell Department of Computer Science Carnegie Mellon University Pittsburgh, PA, USA odonnellcs cmu edu http://www.cs.cmu.edu/ odonnell THEORY OFCOMPUTING, Volume 9 (2013), pp. 579–585585 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
