CS Paper Radar

A Resolution of Friedgut's Conjecture on Influential Coalitions

Eshan Chattopadhyay, Mohit Gurumukhani

cs.CC cs.DM ·submitted 2026-09-14 22:15 UTC · v2
publishedtheory

Abstract

We prove that, for every constant $\varepsilon>0$ and every function $f:Σ^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.

Closest papers

Nearest neighbours by meaning across the whole index.

Large player classes and approximately weighted voting

cs.GT econ.THmath.OC ·2026-10-06 ·Ezra Einy, Ori Haimanko
theory similarity 0.64
Abstract

It is known that completeness of the coalitional ($C$-)desirability relation in a simple game does not imply the existence of a weighted-majority representation. We show that weightedness is implied in an approximate sense. Call an $n$-player simple game $\varepsilon$-weighted if, for some weight vector in the $(n-1)$-simplex, any losing coalition weight exceeds any winning coalition weight by at most $\varepsilon$; let $\varepsilon^{\ast}$ be the smallest such $\varepsilon$. We establish an upper bound on $\varepsilon^{\ast}$ in a general $C$-complete game, and deduce that, if all classes of equally desirable players become large asymptotically but the number of classes is bounded, then $\varepsilon^{\ast}=O(1/n_{\min})$ for the minimal player class size $n_{\min}$, and the bound is tight. Importantly, the minimal attainable fraction $δ$ of coalitions mislabeled by a weighting rule also tends to $0$ when $n_{\min}\rightarrow\infty$ and the number of player classes is bounded, with $δ=O(1/\sqrt{n_{\min}})$.

0.12

Weak Composition Theorems for Randomized Communication

cs.CC ·2026-11-12 ·Pachara Sawettamalya
theory similarity 0.64
Abstract

We present two results towards the randomized communication complexity of composed functions. Our contributions include: - \textbf{Lifting-by-Influence.} For any binary function $f$ and any outer gadget $g:\{0,1\}^n \rightarrow \mathbb{R}$, we show that up to additive terms, computing $g \circ f^n$ information-theoretically requires solving at least $\operatorname{Inf}(g)$ instances of $f$, where $\operatorname{Inf}(g)$ denotes the total influence of $g$. To our knowledge, this is the first composition lower bound for randomized communication that applies to \emph{every} choice of $f$ and $g$. - \textbf{Symmetric Composition.} When $g$ is a symmetric function with a value transition at Hamming weight $d$, we strengthen the number of required instances to $\min\{d,n+1-d\}$. As an implication, this recovers the previously known direct-sum theorem, XOR lemma, and majority lemma. Our proofs develop novel and distinctive usages of the classical \emph{input embedding} argument of Barak, Braverman, Chen, and Rao (SICOMP 2013). As an additional ingredient, we introduce a new public sampling framework that avoids auxiliary communication during the recovery phase of the protocol, ultimately reducing the extra cost from $O(n)$ bits of information to just $O(1)$.

0.06

Almost every Boolean function has central threshold degree

cs.DM cs.ITmath.CO ·2026-10-10 ·Martin Anthony
theory similarity 0.64
Abstract · 12 pages. Revised abstract and exposition to clarify the conjectures resolved; references updated. Results and proofs unchanged

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree either $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$, except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. The paper proves a 1991 conjecture of Aspnes, Beigel, Furst and Rudich. It also proves a 1991 conjecture of Wang and Williams for even $n$ and its main concentration assertion for odd $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

0.36

Stable Voting Rules on the Edge of Optimal Metric Distortion

cs.GT ·2026-09-08 ·Ziyi Cai, Fabian Frank, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang +1 more
theory similarity 0.63
Abstract

We prove the existence of a randomized voting rule with metric distortion at most $2.1248$, within $0.013$ of the lower bound of $2.11264$. Our rule comes from a generalization of \emph{stable $k$-lotteries} developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries. In particular we show that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates, and that stable $2$-lotteries are optimal in this class of voting rules.

0.33

On the most informative Boolean function under noise

cs.IT math.CO ·2026-11-03 ·Dimiter Kramer, Mert Saglam
similarity 0.63
Abstract · 17 pages, 2 figures

Let $X$ be a uniform random bit string and $Y$ be obtained by flipping each bit of $X$ independently with probability $p$. Let $C$ be a random bit obtained as a function of $Y$. We show that $\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X)$ for all $p\in[0,1]$, which resolves a conjecture posed by Courtade and Kumar in 2013.

0.48

The probabilistic bound for perfect hashing is sharp only for binary alphabets

cs.IT math.CO ·2026-11-05 ·Shitao Li, Minjia Shi
theory similarity 0.62
Abstract

We investigate the optimal asymptotic rate $R_q$ of perfect $q$-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let $B_q=-\log_2(1-q!/q^q)/(q-1)$ denote the classical probabilistic lower bound. We prove that $R_q=B_q$ if and only if $q=2$, establishing an explicit strict improvement for every $q\ge3$ and settling the first assertion of a conjecture of Xing and Yuan (Combinatorica 43 (2023), 347--366). More significantly, we show that, for every $η>0$, $R_q\ge B_q+\exp(-(2+η)q)$ for all sufficiently large integers $q$. This improves the previously known increments of scale $\exp(-3q+O(\ln q))$ by an exponential factor. We also establish a structural limitation of the concatenation method. For pairwise uniform inner codes of subexponential length, the resulting rate bound exceeds $B_q$ by at most $\exp(-3q+o(q))$. Thus, exponentially long inner codes are necessary to achieve the new improvement scale within this framework. Our proofs combine Fourier analysis, high-dimensional simplex codes, additive permutation counts, and entropy bounds for hypergraph matchings. We further strengthen lower bounds from short inner codes and improve several known numerical estimates.

0.43

Dictators are most informative

cs.IT math.COmath.PR ·2026-09-21 ·Vu Khac Ky, Tuan Tran
theoryhot directionhighly cited similarity 0.62
Abstract · 36 pages

We prove the Courtade-Kumar conjecture: among all Boolean functions $f\colon \{-1,1\}^n\to\{-1,1\}$, a dictator retains the most information about a uniformly random input observed through independent binary noise.

0.59

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.61
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46