Skip to content

A Resolution of Friedgut's Conjecture on Influential Coalitions

Sep 2026 · Electron. Colloquium Comput. Complex. · Vol TR26 · 1 citation · ⚡ 1 influential · 18 references
Computer Science

Abstract

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.

View source

Similar papers

Preprint Oct 2026

Tameness of transitive Boolean functions

Let $f_n:\{0,1\}^n\to\{0,1\}$ be Boolean functions, and let $C_n$ count their changes in a unit time interval under stationary dynamics in which each coordinate is independently resampled at rate one from the Bernoulli$(p_n)$ distribution. We prove that, if $f_n$ is transitive and $n\min\{p_n,1-p_n\}^{r}\to\infty$ for...

Xin Long · 0 citations
Preprint Sep 2026

The spectrum of $(\xi\alpha^n)$ can be uncountable

In this note, we give a counterexample to the assertion of Problem 10.4 in Bugeaud's monograph Distribution modulo one and Diophantine approximation, which goes back to Mend\`es France. The problem states that the spectrum of the sequence $(\xi\alpha^n)_{n\ge1}$, that is, the set of irrational $\theta\in(0,1)$ for whic...

Hikmet Burak Özcan · 0 citations
Preprint Sep 2026

Disproof of a Conjectured Upper Bound for the Davenport Constant

Let $G= C_{n_1}\oplus\cdots\oplus C_{n_r}$ be a finite abelian group with $1<n_1\mid\cdots\mid n_r$, and let $\rr(G)=r$ denote its rank. The Davenport constant $\DD(G)$ is the least integer $\ell$ such that every sequence of $\ell$ elements of $G$ contains a nonempty zero-sum subsequence, and $\DD^*(G)=1+\sum_{i=1}^r(n...

Guo-Qing Wang · 3 citations · ⚡1
Preprint Sep 2026

A Proof of the Most Informative Boolean Function Conjecture

The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers, and gives a computer-assisted proof of the Courtade--Kumar conjecture.

Zi-Jie Chen, Amin Gohari, Adel Javanmard et al. · 2 citations
Sep 2026

Proof of the Kahn Saks Conjecture

Let $\mathbb{P}(x\prec y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension of an $n$-element poset $P$, and define the balancing coefficient to be $\delta(x,y)=\min(\mathbb{P}(x\prec y),\mathbb{P}(y\prec x))$ with $\delta(P)=\max_{x,y}\delta(x,y)$. We prove (Theorem 1) that sufficiently...

Max Aires · 1 citation
Preprint Oct 2026

Antichains among Divisor Sums of Divisors

For a positive integer $n$, let $S(n)=\{\sigma(d): d\mid n\}$ be ordered by divisibility, and let $a(n)$ be its width. We study how much of the divisor lattice of $n$ survives under the map $d\mapsto \sigma(d)$. For every fixed prime-exponent pattern, the largest possible value of $a(n)$ is the width of a corresponding...

Felix Huber · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.