A Resolution of Friedgut's Conjecture on Influential Coalitions
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A Resolution of Friedgut's Conjecture on Influential Coalitions".
Jane: Here's the gist of the paper. A Resolution of Friedgut’s Conjecture on Influential Coalitions proves that there exists a coalition of size O(n/√log n) coordinates that can force a fixed output with high probability, resolving a conjecture in the field Resolution of Friedgut's Conjecture The paper proves that for every constant ε > 0 and every function f: Σn → 0, 1, there is a coalition of O(n/√log n) coordinates and a target output b ∈ 0, 1 such that the coalition can choose its values to make the output equal to b with probability at least 1 − ε after the remaining coordinates are sampled uniformly and independently This bound is independent of alphabet size and holds for monotone Boolean functions on
0, 1: n as well The result provides the first sublinear bound on the number of bad players needed to force a fixed output with probability at least 1 − ε in any one-round protocol with independent uniform messages, regardless of the message length Lower Bounds and Context The Kahn–Kalai–Linial (KKL) theorem states that every balanced Boolean function f: 0, 1n → 0, 1 has a coordinate with influence at least Ω(log n/n) This implies that a small coalition of coordinates can almost determine the output However, for functions f: Σn → 0, 1 over an arbitrary finite alphabet Σ, a sublinear coalition does not suffice with a bound independent of Σ The paper resolves Friedgut’s conjecture by showing that the required coalition size is O(n/√log n) in both the finite-alphabet and continuous settings Proof Strategy for Monotone Functions For monotone functions f:
r: n → 0, 1, the proof proceeds by decreasing the expectation towards 0 as long as possible If the expectation falls below ε, a small coalition forces the opposite output The key ingredient is Lemma 3.3, which states that if E
h: ≥ ε and J0(h) ≤ τ, then a coalition of exp(O(τ2)) coordinates can force 1 with probability at least 1 − ε This lemma is derived by encoding each coordinate by independent p-biased bits and applying Theorem 3.4 Key Technical Lemmas The proof relies on several technical lemmas, including Claim 2.2, which shows that for every Borel measurable function f:
0, 1: n → 0, 1, there exists a monotone function g such that E
g: = E
f: and P b S(g) ≤ P b S(f) Claim 2.3 shows how to discretize a monotone function while approximately preserving its expectation and the probability that any coalition can force either output, yielding E
f: − E
g: ≤ n/√r and P b S(g) − P b S(f) ≤ n/√r Lemma 3.5 establishes a relationship between the p-biased influence of an encoded function and the influence towards 0 of the original function, which is crucial for applying Hatami's theorem The algorithm to find such a B terminates in finite steps, leading to a coalition size bounded by O(n/√log n) or exp(CLemma 3.3 · (δ · n)2), which is o(n/p log(n)) By monotonicity of f, this coalition biases the output towards 1 even without controlling previously fixed coordinates The final result shows that for monotone or Borel measurable Boolean functions on
0, 1: n, there exists a set B with B ≤ C · √ n log(n) such that P b B(f) ≥ 1 − ε The result also applies to continuous settings Connection to Collective Coin Flipping The study connects to collective coin flipping, where players try to agree on a random bit despite adversarial faults In the full information model, controlling a player allows the adversary to choose that coordinate after observing all coordinates outside the coalition While KKL shows O(n/log n) bad players suffice for single-bit messages, this result provides a better bound of O(n/√log n) regardless of message length The encoding scheme relates the influence of a function on a product space to the p-biased influence of the encoded function Proof Details for Lemma 3.5 Lemma 3.5 is proved by setting p = min ε2/rn and τ2r · n2 so that prn ≤ ε2/2 and 4prn·2 ≤ 2τ This allows the application of Lemma 3.5 to function f with parameters ε2, obtaining a function g: 0, 1m → 0, 1 for some m ∈ N The proof involves encoding each coordinate so that every nonconstant threshold of its encoded value is an OR of some of its bits This property allows bounding the p-biased influence of the encoded function by 2 J0(f, A) The final step uses Theorem 3.4 with parameter εT to find a coalition S with S ≤ exp(C · τ2) such that P 1 S(g, µp) ≥ 1 − ε2 Approximating the Uniform Distribution The encoding uses a max selector function ϕa: 0, 1l →
r: as defined in Definition 4.1 Lemma 4.3 shows that there exists a sequence a such that for all i ∈
r: , Pr y∼µp
ϕa(y) = i: − 1/r ≤ 2p This leads to the bound A − Ur∞ ≤ 2p The influence of f towards 0 under A is bounded by J0(f, A) ≤ J0(f) + 2pr · n2 This bound is essential for proving Lemma 3.5 Final Bound Derivation The analysis of the algorithm shows that if it terminates by setting b = 1, the coalition size is at most exp(CLemma 3.3 · (δ · n)2) = o(n/p log(n)) By monotonicity of f, P 1 B(f) ≥ Pr x
f(x−B, rB) = 1: ≥ 1 − ε This confirms the desired coalition size of O(n/√log n) The same result holds for monotone or Borel measurable functions on
0, 1: n Acknowledgements and References M.G.
Paper summary: Tom: So, looking at "A Resolution of Friedgut's Conjecture on Influential Coalitions," the authors have provided this sublinear bound of n over the square root of log n for forcing a fixed output with high probability that was independent of the alphabet size.
Jane: They did this by showing that for monotone functions on zero onen, you can force an output with probability at least one minus epsilon using a coalition of coordinates whose size is bounded by c times square root n times log n <ref:2609.16401#pg1,functions on 0, 1 n>.
Lu: The authors used a proof strategy where they decrease the expectation towards zero as long as possible, and when it drops below epsilon, a small coalition forces the opposite output.
Meng: I think what stands out is that even though they are dealing with complex functions on zero onen, this result holds for monotone or Borel measurable functions on that domain <ref:2609.16401#pg1,functions on 0, 1 n>.
Lalam: The paper connects this to collective coin flipping and gives the first sublinear bound on the number of bad players needed for one round with independent uniform messages regardless of message length.
Tom: It really settles a conjecture in the field by showing that repeatedly applying bounds from Kahn Kalai Linial doesn't give the same coalition guarantee when you move to finite alphabets.
Jane: The main implication is that we now have a much tighter and more general understanding of how many inputs are needed to exert control over an output in these kinds of settings.
Lu: It shows that for functions with some regularity, like monotonicity, there’s a concrete limit on the size of the coalition required to force a fixed output with high probability.
Meng: For practical AI development, this means we can start thinking about how small a subset of inputs could be enough to significantly impact the final decision in certain scenarios.
Lalam: It’s about finding that set B with size bounded by c times square root n times log n for monotone or Borel measurable functions on zero onen <ref:2609.16401#pg1,functions on 0, 1 n>.
Conclusion: Tom: So, to wrap up this section, we’re looking at Tom and Jane talking about "A Resolution of Friedgut's Conjecture on Influential Coalitions." Basically, they proved you can force a specific outcome with high probability using a relatively small group of inputs.
Jane: That’s the big picture. The main idea is that for these kinds of functions, like monotone ones, you don't need to check every single input to make sure the result stays fixed. You just need this specific size of a coalition.
Lu: What’s important here is that this works even when we’re dealing with continuous settings on the unit square instead of just discrete bits. That makes it much more general than some previous work.
Meng: For us, what does that mean in terms of running things? It means we can predict how many coordinates a small set of players needs to control to guarantee a certain result in our system, which helps us figure out where the complexity truly lies at scale.
Lalam: I think what’s striking is that this bound on the size of that coalition is independent of how big the alphabet or the message length gets. That makes it very robust for real-world problems we actually deal with.
Tom: So, we have this result: a coalition of about square root n times log n coordinates can force an output with high confidence in any one round protocol. It settles that conjecture Friedgut was working on—the one about how much influence is actually needed.
Jane: Exactly. It moves the needle from needing a huge fraction of inputs to needing just a sublinear amount for many important function types, like the monotone ones they studied first.
Lu: The method itself relies on some pretty heavy technical machinery, involving encoding functions and bounding expectations using something called Hatami's theorem. It’s mathematically dense, but the resulting bound is solid.
Meng: I’m curious about what happens if we try to apply this to a really complex function that isn't monotone? Does the complexity of the function itself break this square root log n rule, or is it always safe?
Lalam: The paper does address that too. They show that for Borel measurable functions on the continuous unit square, you get a similar bound, which means this result really has broad applicability across different types of mathematical problems.
Cornell University
cs.CC, cs.DM
Submitted: 2026-09-14
Updated: 2026-11-05
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 82/100
The gist: A Resolution of Friedgut’s Conjecture on Influential Coalitions proves that there exists a coalition of size O(n/√log n) coordinates that can force a fixed output with high probability…
Key concepts
- Friedgut's Conjecture
- This conjecture deals with the minimum number of coordinates required to force a specific output in a function. The paper proves that this minimum coalition size is bounded by O(n/√log n), which is a significant improvement over existing bounds for forcing fixed outputs.
- Kahn–Kalai–Linial (KKL) Theorem
- This theorem states that every balanced Boolean function has at least one coordinate with influence of Ω(log n/n). While this suggests small coalitions can be influential, the paper shows that for general functions over finite alphabets, a sublinear coalition size is not sufficient without considering other factors.
- Monotone Functions
- These are functions where increasing the input values never decreases the output. The proof strategy for monotone functions involves decreasing an expectation towards zero. If it falls below a threshold ε, a small set of coordinates can force the opposite output with high probability.
- Lemma 3.3
- This key lemma provides a mechanism to find a coalition size based on the expected value and influence of an encoded function. It states that if the expected value is large enough (≥ ε) and its influence is small enough, a coalition of exp(O(τ²)) coordinates can force an output with probability at least 1 - ε.
Terminology
Summary
A Resolution of Friedgut’s Conjecture on Influential Coalitions proves that there exists a coalition of size O(n/√log n) coordinates that can force a fixed output with high probability, resolving a conjecture in the field
Resolution of Friedgut's Conjecture
The paper proves that for every constant ε > 0 and every function f: Σn → 0, 1, there is a coalition of O(n/√log n) coordinates and a target output b ∈ 0, 1 such that the coalition can choose its values to make the output equal to b with probability at least 1 − ε after the remaining coordinates are sampled uniformly and independently This bound is independent of alphabet size and holds for monotone Boolean functions on [0, 1]n as well The result provides the first sublinear bound on the number of bad players needed to force a fixed output with probability at least 1 − ε in any one-round protocol with independent uniform messages, regardless of the message length
Lower Bounds and Context
The Kahn–Kalai–Linial (KKL) theorem states that every balanced Boolean function f: 0, 1n → 0, 1 has a coordinate with influence at least Ω(log n/n) This implies that a small coalition of coordinates can almost determine the output However, for functions f: Σn → 0, 1 over an arbitrary finite alphabet Σ, a sublinear coalition does not suffice with a bound independent of Σ The paper resolves Friedgut’s conjecture by showing that the required coalition size is O(n/√log n) in both the finite-alphabet and continuous settings
Proof Strategy for Monotone Functions
For monotone functions f: [r]n → 0, 1, the proof proceeds by decreasing the expectation towards 0 as long as possible If the expectation falls below ε, a small coalition forces the opposite output The key ingredient is Lemma 3.3, which states that if E[h] ≥ ε and J0(h) ≤ τ, then a coalition of exp(O(τ2)) coordinates can force 1 with probability at least 1 − ε This lemma is derived by encoding each coordinate by independent p-biased bits and applying Theorem 3. p. 3 1 for a
formal definition. ) The consequence of Hatami’s theorem that we use states that for a monotone function
on independent p-biased bits (where 0 < p ≤ 1/2), with expectation at least ε and total p-biased influence
at most τ , a coalition of exp(O(τ
2
)) bits can force the output to be 1 with probability at least 1 − ε.Where the paper says it
Key Technical Lemmas
The proof relies on several technical lemmas, including Claim 2.2, which shows that for every Borel measurable function f: [0, 1]n → 0, 1, there exists a monotone function g such that E[g] = E[f] and P b S(g) ≤ P b S(f) Claim 2. p. 5 This follows from the following monotonization lemma, proved
using a sifting argument similar to those in [BL85, KKL88, BKKKL92]. For every Borel measurable function f : [0, 1]n → {0, 1}, there exists a monotone function
g : [0, 1]n → {0, 1} such that E[g] = E[f] and, for all S ⊆ [n] and b ∈ {0, 1}, it holds that P
b
S
(g) ≤ P
b
S
(f). Discretizing Boolean Functions We next show how to discretize a monotone function while approximately preserving its expectation and the probability that any coalition can force either output. For all n, r ∈ N, with r ≥ 2, the following holds.Where the paper says it
Where the paper says it
Conclusion and Application
The algorithm to find such a B terminates in finite steps, leading to a coalition size bounded by O(n/√log n) or exp(CLemma 3.3 · (δ · n)2), which is o(n/p log(n)) By monotonicity of f, this coalition biases the output towards 1 even without controlling previously fixed coordinates The final result shows that for monotone or Borel measurable Boolean functions on [0, 1]n, there exists a set B with B ≤ C · √ n log(n) such that P b B(f) ≥ 1 − ε The result also applies to continuous settings
Connection to Collective Coin Flipping
The study connects to collective coin flipping, where players try to agree on a random bit despite adversarial faults In the full information model, controlling a player allows the adversary to choose that coordinate after observing all coordinates outside the coalition While KKL shows O(n/log n) bad players suffice for single-bit messages, this result provides a better bound of O(n/√log n) regardless of message length The encoding scheme relates the influence of a function on a product space to the p-biased influence of the encoded function
Proof Details for Lemma 3.5
Lemma 3.5 is proved by setting p = min ε2/rn and τ2r · n2 so that prn ≤ ε2/2 and 4prn·2 ≤ 2τ This allows the application of Lemma 3. p. 9 Proof of Lemma 3. We let
p = min ε
2rn
,
τ
2r · n2
so that prn ≤
ε
2
and 4prn·
2 ≤ 2τ . The main idea is to encode each coordinate so that every nonconstant threshold of its encoded value is an OR of some of its bits. Since fixing all other coordinates of a
monotone function leaves a threshold or a constant function, this will let us bound the p-biased influence of
the encoded function by the influence of f towards 0.Where the paper says it
Where the paper says it
Approximating the Uniform Distribution
The encoding uses a max selector function ϕa: 0, 1l → [r] as defined in Definition 4.1 Lemma 4.3 shows that there exists a sequence a such that for all i ∈ [r], Pr y∼µp[ϕa(y) = i] − 1/r ≤ 2p This leads to the bound A − Ur∞ ≤ 2p The influence of f towards 0 under A is bounded by J0(f, A) ≤ J0(f) + 2pr · n2 This bound is essential for proving Lemma 3. p. 9 Since fixing all other coordinates of a
monotone function leaves a threshold or a constant function, this will let us bound the p-biased influence of
the encoded function by the influence of f towards 0. We first prove this influence bound, then choose the
encoding to approximate the uniform distribution, and finally complete the proof of Lemma 3.Where the paper says it
Final Bound Derivation
The analysis of the algorithm shows that if it terminates by setting b = 1, the coalition size is at most exp(CLemma 3.3 · (δ · n)2) = o(n/p log(n)) By monotonicity of f, P 1 B(f) ≥ Pr x[f(x−B, rB) = 1] ≥ 1 − ε This confirms the desired coalition size of O(n/√log n) The same result holds for monotone or Borel measurable functions on [0, 1]n
Acknowledgements and References
M.G.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Sublinear coalition forcing for collective coin flipping: The improved system can force a fixed output with probability at least 1 minus epsilon in any one-round protocol with independent uniform messages regardless of message length, achieving a bound of O(n/sqrt(log n)).
-
Generalization to finite alphabets: The system can resolve Friedgut’s conjecture for Boolean functions on an arbitrary finite alphabet Σ, providing a coalition size bound of O(n/sqrt(log n)) independent of the alphabet size Σ.
-
Analysis in monotone settings: For monotone functions on [r]n, the system can find a coalition of size at most C times sqrt(n) log n that forces an output with probability at least 1 minus epsilon.
Abstract
We prove that, for every constant epsilon>0 and every function f:Σ n to0, 1, there is a coalition of O(n/sqrt n) coordinates and a target output b in0, 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-epsilon. 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/ 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-epsilon 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.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?