me programme

CMU Theory lunch talk from November 7, 2018, by Paul Goelz on The Fluid Mechanics of Liquid Democracy. Liquid democracy is the principle of making collective decisions by letting agents transitively delegate their votes. Despite its significant appeal, it has become apparent that a weakness of liquid democracy is that a small subset of agents may gain massive influence. To address this, we propose to change the current practice by allowing agents to specify multiple delegation options instead of just one. Much like in nature, where — fluid mechanics teaches us — liquid maintains an equal level in connected vessels, so do we seek to control the flow of votes in a way that balances influence as much as possible. Specifically, we analyze the problem of choosing delegations to approximately minimize the maximum number of votes entrusted to any agent, by drawing connections to the literature on confluent flow. We also introduce a random graph model for liquid democracy, and use it to demonstrate the benefits of our approach both theoretically and empirically.

CMU Theory lunch talk from February 27, 2019 by Akshayaram Srinivasan on Leakage-Resilient Secret Sharing A secret sharing scheme allows a dealer to share a secret among a set of n parties such that any authorized subset of the parties can recover the secret, while any unauthorized subset learns no information about the secret. A leakage-resilient secret sharing scheme (introduced in independent works by Goyal and Kumar, STOC ’18 and Benhamouda, Degwekar, Ishai and Rabin, CRYPTO ’18) additionally requires the secrecy to hold against every unauthorized set of parties even if they obtain some bounded leakage from every other share. The leakage is said to be local if it is computed independently for each share. So far, the only known constructions of local leakage resilient secret sharing schemes are for threshold access structures for very low (O(1)) or very high (n-o(log n)) thresholds. In this work, we give a compiler that takes a secret sharing scheme for any monotone access structure and produces a local leakage resilient secret sharing scheme for the same access structure, with only a constant factor asymptotic blow-up in the sizes of the shares. Furthermore, the resultant secret sharing scheme has optimal leakage-resilience rate, i.e., the ratio between the leakage tolerated and the size of each share can be made arbitrarily close to 1. Based on joint work with Prasanth Vasudevan.

CMU Theory lunch talk from October 17, 2018, by Chris Cox on Small Antipodal Spherical Codes. An antipodal spherical ε-code in ℝ^d is a collection of vectors X ⊆ S^(d-1) for which |⟨x,y⟩| ≤ ε for all x≠y∈X. Such codes can be viewed as a generalization of Hamming codes in 𝔽_2^d where all distances lie within [1/2*(1-ε)*d,1/2*(1+ε)*d]. In this talk, we'll be interested in the parameter θ(d,k), which is the smallest ε for which there is an antipodal spherical ε-code in ℝ^d with d+k vectors. In other words, θ(d,k) is the answer to the question "how can d+k vectors in ℝ^d be arranged so that they are as close to orthogonal as possible?" We focus on the case when k is fixed and d→∞, that is, when the code has a small excess number of vectors compared to the dimension. We find an intimate relationship between determining θ(d,k) and the existence of (k+1 choose 2) equiangular lines in ℝ^k; thus, we are able to pin down θ(d,k) precisely for k ∈ {0,1,2,3,7,23} and establish asymptotics for general k. Usually when studying spherical codes, one uses linear programming techniques, but the main tool in our result is instead a tight upper bound on 𝔼_{x, y~μ}|⟨x,y⟩| whenever μ is an isotropic probability mass on ℝ^k, which may be of independent interest. Our results translate naturally to the analogous question in ℂ^d, in which case the question relates to the existence of k^2 equiangular lines in ℂ^k, also known as SIC-POVM in physics literature. (Joint work with Boris Bukh)

CMU Theory lunch talk from September 5, 2018, by Nicolas Resch on Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs. For a vector space F^n over a field F, an (η, ß)-dimension expander of degree d is a collection of d linear maps Γ_j : F^n \to F^n such that for every subspace U of F^n of dimension at most ηn, the image of U under all the maps, ∑_{j=1}^d Γ_j(U), has dimension at least ßdim(U). Over a finite field, a random collection of d=O(1) maps Γ_j over excellent “lossless” expansion with high probability: ß ≈ d for η ≥ Ω(1/\eta). When it comes to a family of explicit constructions (for growing n), however, achieving even expansion factor β = 1 + ε with constant degree is a non-trivial goal. We present an explicit construction of dimension expanders over finite fields based on linearized polynomials and subspace designs, drawing inspiration from recent progress on list decoding in the rank-metric. Our approach yields the following: Lossless expansion over large fields; more precisely ß ≥ (1–ε)d and η ≥ (1–ε)/d with d=O_ε(1), when |F| ≥ Ω(n). Optimal up to constant factors expansion over fields of arbitrarily small polynomial size; more precisely ß ≥ Ω(δd) and η ≥ Ω(1/(δd)) with d = O_δ(1), when |F| ≥ n^δ. Previously, an approach reducing to monotone expanders (a form of vertex expansion that is highly non-trivial to establish) gave (Ω(1), 1+Ω(1))-dimension expanders of constant degree over all fields. An approach based on “rank condensing via subspace designs” led to dimension expanders with ß ≥ Ω(√d) over large finite fields. Ours is the first construction to achieve lossless dimension expansion, or even expansion proportional to the degree. Based on joint work with Venkatesan Guruswami and Chaoping Xing.

CMU Theory lunch talk from October 31, 2018, by Yihan Zhang on Quadratically Constrained Myopic Adversarial Channels. Abstract: We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most O(log(n)) bits in one sub-regime, and at most O(n^(1+ε)) bits for any ε greater than 0 in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be of independent interest. Joint work with Shashank Vatedka (CUHK, now moving to Télécom ParisTech), Sidharth Jaggi (CUHK) and Anand D. Sarwate (Rutgers SUNJ).

CMU Theory lunch talk from February 6, 2019 by Goran Zuzic on Byzantine Secretary Problem. In the classical secretary problem, a sequence of n elements arrive in a uniformly random order. The goal is to maximize the probability of selecting the largest element (or to maximize the expected value of the selected item). This model captures applications like online auctions, where we want to select the highest bidder. In many such applications, however, one may expect a few outlier arrivals that are adversarially placed in the arrival sequence. Can we still select a large element with good probability? Dynkin's popular 1/e -secretary algorithm is sensitive to even a single adversarial arrival: if the adversary gives one large bid at the beginning of the stream, the algorithm does not select any element at all. In this talk we introduce the Byzantine Secretary problem where we have two kinds of elements: green (good) and red (bad). The green elements arrive uniformly at random. The reds arrive adversarially. The goal is to find a large green element. It is easy to see that selecting the largest green element is not possible even when a small fraction of the arrival is red, i.e., we cannot do much better than random guessing. Hence we introduce the \emph{second-max} benchmark, where the goal is to select the second-largest green element or better. This dramatically improves our results. We give an explicit polylog∗n competitive algorithm, using a multi-layered bucketing scheme that adaptively refines our estimates of second-max as we see more elements. For the multiple secretary problem, where we can pick up to r secretaries, we show constant competitiveness as long as r is large enough. For this, we give an adaptive thresholding algorithm that raises and lowers thresholds depending on the quality and quantity of recently selected elements.