Abstract. Lionel Levine’s hat challenge has [Formula: see text] players, each with a (very large or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine’s conjecture is that the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to problems in graph theory: relating the size of the largest independent set in a graph and in a random induced subgraph of it, and bounding the size of a set of vertices intersecting every maximum-size independent set in a graph.

An important element of social choice theory are impossibility theorems, such as Arrow's theorem [1] and Gibbard-Satterthwaite's theorem [2], [3], which state that under certain natural constraints, social choice mechanisms are impossible to construct. In recent years, beginning in Kalai [4], much work has been done in finding robust versions of these theorems, showing that impossibility remains even when the constraints are almost always satisfied. In this work we present an Algebraic scheme for producing such results. We demonstrate it for a variant of Arrow's theorem, found in Dokow and Holzman [5].

The Gibbard–Satterthwaite theorem states that every nondictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard–Satterthwaite theorem: a random manipulation by a single random voter will succeed with a nonnegligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range.

The Gibbard-Satterthwaite theorem states that every non-trivial voting method among at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with non-negligible probability for every neutral voting method among 3 alternatives that is far from being a dictatorship.

A theorem of Bourgain [4] on Fourier tails states that if f :(-1, 1)n → (-1, 1) is a boolean-valued function on the discrete cube such that for any k > 0, [Σ|S| > k f(S)2 < k-1/2 + o(1), ] then essentially, f depends on only 2O(k) coordinates. This and related theorems such as Friedgut's Theorem [12], KKL [16], the FKN Theorem [14], and the Majority Is Stablest Theorem [27] have proven useful for numerous results in theoretical computer science [3, 5, 9, 6, 7, 10, 11, 18, 19, 20, 24, 17, 25, 23, 22, 28, 29, 31].In this paper we prove an analogue to Bourgain's Theorem for bounded functions on the discrete cube, f : (n ⋺ [-1,1]); such functions arise naturally in hardness-of-approximation problems, as averages of boolean functions. Specifically, we show that for every k > 0, if [Σ|S| > k f(S)2 < exp(-O(k2 log k))] then essentially, f depends on only 2O(k) coordinates. We also show, perhaps surprisingly, that this result is sharp up to the log k factor in the exponent.Our proof uses Fourier analysis, as well as some extremal properties of the Chebyshev polynomials.