Influential Coalitions for Boolean Functions I: Constructions

by Jean Bourgain, Jeff Kahn, and Gil Kalai

Theory of Computing, Volume 20(4), pp. 1-13, 2024

Bibliography with links to cited articles

[1]   Miklós Ajtai and Nathan Linial: The influence of large coalitions. Combinatorica, 13(2):129–145, 1993. [doi:10.1007/BF01303199]

[2]   Noga Alon, Guy Moshkovitz, and Noam Solomon: Traces of hypergraphs. J. London Math. Soc., 100(2):498–517, 2019. [doi:10.1112/jlms.12233]

[3]   Michael Ben-Or and Nathan Linial: Collective coin flipping. In Silvio Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pp. 91–115. JAI Press, 1989. DSpace@MIT. Preliminary version in FOCS’85.

[4]    Béla Bollobás and Andrew J Radcliffe: Defect Sauer results. J. Combin. Theory–A, 72(2):189–208, 1995. [doi:10.1016/0097-3165(95)90060-8]

[5]   John Adrian Bondy: Induced subsets. J. Combin. Theory–B, 12(2):201–202, 1972. [doi:10.1016/0095-8956(72)90025-1]

[6]   Jean Bourgain, Jeff Kahn, and Gil Kalai: Influential coalitions for Boolean functions, 2014. [arXiv:1409.3033]

[7]   Benny Chor: Private communication, circa 1990.

[8]   Péter Frankl: On the trace of finite sets. J. Combin. Theory–A, 34(1):41–45, 1983. [doi:10.1016/0097-3165(83)90038-9]

[9]   Sergiu Hart: A note on the edges of the n-cube. Discr. Math., 14(2):157–163, 1976. [doi:10.1016/0012-365X(76)90058-3]

[10]   Svante Janson, Tomasz Łuczak, and Andrzej Ruciński: Random Graphs. Wiley, 2000. [doi:10.1002/9781118032718]

[11]   Jeff Kahn and Gil Kalai: Thresholds and expectation thresholds. Combin. Probab. Comput., 16(3):495–502, 2007. [doi:10.1017/S0963548307008474]

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

[13]   Gil Kalai: Nati’s influence. Combinatorics and More, Gil Kalai’s blog, May 2008. LINK.

[14]   Nathan Linial: Open problem. In Jeff Kahn, Angelika Steger, and Benny Sudakov, editors, Oberwolfach Report No. 01/2011, pp. 75–76. 2011. LINK.

[15]   Norbert Sauer: On the density of families of sets. J. Combin. Theory–A, 13(1):145–147, 1972. [doi:10.1016/0097-3165(72)90019-2]

[16]   Saharon Shelah: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math, 41(1):247–261, 1972. Project Euclid.

[17]   Vladimir N. Vapnik and Alexei Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. Reproduced in Measure of Complexity: Festschrift for Alexei Chervonenkis, Springer 2015. [doi:10.1137/1116025]

[18]   Wikipedia: Bernstein inequalities (probability theory). Accessed 06-09-2024.