Metraipolis › archive › dc_8eb651852012

A Resolution of Friedgut's Conjecture on Influential Coalitions — arXiv:2609.16401

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.16401
License (as archived): CC0-1.0
Archived: 2026-10-15T22:00:17.618Z
SHA-256 of the archived text: 9da59bb07fb300e543b2eb0823aa6c67449f8fe3b220297b5c60ba8d7250b933
Stable URL of this page: https://metraipolis.com/documento/dc_8eb651852012

How to cite

A Resolution of Friedgut's Conjecture on Influential Coalitions — arXiv:2609.16401 — arXiv (en), https://arxiv.org/abs/2609.16401 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8eb651852012 (Metraipolis archive dc_8eb651852012, sha256 9da59bb07fb300e543b2eb0823aa6c67449f8fe3b220297b5c60ba8d7250b933)

BibTeX

@misc{dc8eb651852012,
  title = {A Resolution of Friedgut's Conjecture on Influential Coalitions — arXiv:2609.16401},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16401},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8eb651852012; sha256 9da59bb07fb300e543b2eb0823aa6c67449f8fe3b220297b5c60ba8d7250b933},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16401. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.16401 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:49:12.504Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).