A Resolution of Friedgut's Conjecture on Influential Coalitions

summary

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…

In short

The paper resolves Friedgut's conjecture by proving that for any function f, a coalition of O(n/√log n) coordinates can force a fixed output with high probability. This is a sublinear bound, meaning fewer coordinates are needed than previously known bounds for certain problems. The result holds for monotone and Borel measurable functions in both finite and continuous settings.

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 used across episodes

This episode discusses

The paper

A Resolution of Friedgut's Conjecture on Influential Coalitions · Read on arXiv

Cornell University

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.

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.

More episodes

← Home