Condorcet’s paradox is a fundamental result in social choice theory which states that there exist elections in which, no matter which candidate wins, a majority of voters prefer a different candidate. In fact, even if we can select any \(k\) winners, there still may exist another candidate that would beat each of the winners in a majority vote. That is, elections may require arbitrarily large dominating sets.

In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that selects a candidate with minimal total distance to the voters. However, the voting rule has limited information about the distances in the metric, such as each voter's ordinal rankings of the candidates in order of distances. The central question is whether we can design rules that, for any election and underlying metric space, select a candidate whose total cost deviates from the optimal by only a small factor, referred to as the distortion.

A cornerstone of social choice theory is Condorcet’s paradox which says that in an election where n voters rank m candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters? Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet winning set. They showed that winning sets of size 2 may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size 6 always exist, regardless of the number of candidates or the number of voters. More generally, we show that if α/1 − lnα ≥ 2/k + 1, then there always exists a committee of size k such that less than an α fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all k ≥ 2. Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection. We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support.

We consider the following well studied problem of metric distortion in social choice. Suppose we have an election with n voters and m candidates who lie in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, each voter gives us a ranked list of the candidates in order of distance. Can we design a rule that regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion)?

We consider the following well-studied problem of metric distortion in social choice. Suppose that we have an election with n voters and m candidates located in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, the voting rule obtains, from each voter, a ranked list of the candidates in order of distance. Can we design a rule that, regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion )? A long line of work culminated in finding optimal deterministic voting rules with metric distortion 3. However, for randomized voting rules, there is still a significant gap in our understanding: even though the best lower bound is substantially lower at 2.112, the best upper bound is still 3, which is attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 - ɛ for some constant ɛ has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. In particular, such a voting rule must use information beyond aggregate comparisons between pairs of candidates, and cannot only assign positive probability to candidates that are voters’ top choices. In this work, we give a rule that guarantees distortion less than 2.753. To do so, we study a handful of voting rules that are new to the problem. One is Maximal Lotteries , a rule based on the Nash equilibrium of a natural zero-sum game that dates back to the 1960s. The others are novel rules that can be thought of as hybrids of Random Dictatorship and the Copeland rule. None of these rules can beat distortion 3 alone; however, a careful randomization between Maximal Lotteries and any of the novel rules can.

Suppose that we have n agents and n items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their matched items is as small as possible. However, instead of having direct access to distances in the metric, we only have each agent's ranking of the items in order of distance. Given this limited information, what is the minimum possible worst-case approximation ratio (known as the distortion) that a matching mechanism can guarantee?

We study the complexity of computing majority as a composition of local functions: Maj_n = h(g_1,…,g_m), where each g_j: {0,1}ⁿ → {0,1} is an arbitrary function that queries only k ≪ n variables and h: {0,1}^m → {0,1} is an arbitrary combining function. We prove an optimal lower bound of m ≥ Ω(n/k log k) on the number of functions needed, which is a factor Ω(log k) larger than the ideal m = n/k. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority. Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits. Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions g_j, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).

Consider the following social choice problem. Suppose we have a set of n voters and m candidates that lie in a metric space. The goal is to design a mechanism to choose a candidate whose average distance to the voters is as small as possible. However, the mechanism does not get direct access to the metric space. Instead, it gets each voter's ordinal ranking of the candidates by distance. Given only this partial information, what is the smallest worst-case approximation ratio (known as the distortion) that a mechanism can guarantee? A simple example shows that no deterministic mechanism can guarantee distortion better than 3, and no randomized mechanism can guarantee distortion better than 2. It has been conjectured that both of these lower bounds are optimal, and recently, Gkatzelis, Halpern, and Shah proved this conjecture for deterministic mechanisms. We disprove the conjecture for randomized mechanisms for m ≥ 3 by constructing elections for which no randomized mechanism can guarantee distortion better than 2.0261 for m = 3, 2.0496 for m = 4, up to 2.1126 as m → ∞. We obtain our lower bounds by identifying a class of simple metrics that appear to capture much of the hardness of the problem, and we show that any randomized mechanism must have high distortion on one of these metrics. We provide a nearly matching upper bound for this restricted class of metrics as well. Finally, we conjecture that these bounds give the optimal distortion for every m, and provide a proof for m = 3, thereby resolving that case.

We study the complexity of small-depth Frege proofs and give the first tradeoffs between the size of each line and the number of lines. Existing lower bounds apply to the overall proof size-the sum of sizes of all lines-and do not distinguish between these notions of complexity. For depth-d Frege proofs of the Tseitin principle where each line is a size-s formula, we prove that$\exp(n/2^{\Omega(d\sqrt{\log s})})$many lines are necessary. This yields new lower bounds on line complexity that are not implied by$\mathbf{H}\mathop{\mathbf{a}}\!\!\!\!^{\circ}\mathbf{stad}$'s recent$\exp(n^{\Omega(1/d)})$lower bound on the overall proof size. For$s$= poly$(n)$, for example, our lower bound remains$\exp(n^{1-o(1)})$for all$d=o(\sqrt{\log n})$, whereas$\mathbf{H}\mathop{\mathbf{a}}\!\!\!\!^{\circ}\mathbf{stad}$'s lower bound is$\exp(n^{o(1)})$once$d\ = \omega_{n}(1)$. Our main conceptual contribution is the simple obser-vation that techniques for establishing correlation bounds in circuit complexity can be leveraged to establish such tradeoffs in proof complexity.

In most notions of locality in error correcting codes-notably locally recoverable codes (LRCs) and locally decodable codes (LDCs)-a decoder seeks to learn a single symbol of a message while looking at only a few symbols of the corresponding codeword. However, suppose that one wants to recover r > 1 symbols of the message. The two extremes are repeating the single-query algorithm r times (this is the intuition behind LRCs with availability, primitive multiset batch codes, and PIR codes) or simply running a global decoding algorithm to recover the whole thing. In this paper, we investigate what can happen in between these two extremes: at what value of r does repetition stop being a good idea? In order to begin to study this question we introduce robust batch codes, which seek to find r symbols of the message using m queries to the codeword, in the presence of erasures. We focus on the case where r = m, which can be seen as a generalization of the MDS property. Surprisingly, we show that for this notion of locality, repetition is optimal even up to very large values of r = Ω(k).