pith. machine review for the scientific record. sign in

arxiv: 1409.3033 · v1 · submitted 2014-09-10 · 🧮 math.CO

Recognition: unknown

Influential coalitions for Boolean Functions

Authors on Pith no claims yet
classification 🧮 math.CO
keywords functionscoalitionslargebooleaninfluentiallatebennybounds
0
0 comments X
read the original abstract

We improve results of Kahn, Kalai, and Linial from the late 80s on the existence of influential large coalitions for Boolean functions, and we give counterexamples to conjectures (of Benny Chor and others) also from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions. The large gaps between the new upper and lower bounds leave a lot of room for further study.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.