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.