We introduce and study the model of list learning with attribute noise. Learning with attribute noise was introduced by Shackelford and Volper (COLT 1988) as a variant of PAC learning in which the algorithm has access to noisy examples and uncorrupted labels, and the goal is to recover an accurate hypothesis. Sloan (COLT 1988) and Goldman and Sloan (Algorithmica 1995) discovered information-theoretic limits to learning in this model, which have impeded further progress. In this article we extend the model to that of list learning, drawing inspiration from the list-decoding model in coding theory, and its recent variant studied in the context of learning. On the positive side, we show that sparse conjunctions can be efficiently list learned under some assumptions on the underlying ground-truth distribution. On the negative side, our results show that even in the list-learning model, efficient learning of parities and majorities is not possible regardless of the representation used. Joint work with Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie

We present online algorithms for directed spanners and directed Steiner forests. These are well-studied network connectivity problems that fall under the unifying framework of online covering and packing linear programming formulations. This framework was developed in the seminal work of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and is based on primal-dual techniques. Specifically, our results include the following: 1. For the pairwise spanner problem, in which the pairs of vertices to be spanned arrive online, we present an efficient randomized algorithm with competitive ratio $\tilde{O}(n^{4/5})$ for graphs with general lengths, where $n$ is the number of vertices of the given graph. For graphs with uniform lengths, we give an efficient randomized algorithm with competitive ratio $\tilde{O}(n^{2/3+\epsilon})$, and an efficient deterministic algorithm with competitive ratio $\tilde{O}(k^{1/2+\epsilon})$, where $k$ is the number of terminal pairs. To the best of our knowledge, these are the first online algorithms for directed spanners. In the offline version, the current best approximation ratio for uniform edge lengths is $\tilde{O}(n^{3/5 + \epsilon})$, due to Chlamtac, Dinitz, Kortsarz, and Laekhanukit (TALG 2020). 2. For the directed Steiner forest problem with uniform costs, in which the pairs of vertices to be connected arrive online, we present an efficient randomized algorithm with competitive ratio $\tilde{O}(n^{2/3 + \epsilon})$. The state-of-the-art online algorithm for general costs is due to Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP 2018) and is $\tilde{O}(k^{1/2 + \epsilon})$-competitive. In the offline version, the current best approximation ratio with uniform costs is $\tilde{O}(n^{3/5 + \epsilon})$, due to Chlamtac, Dinitz, Kortsarz, and Laekhanukit (TALG 2020). To obtain efficient and competitive online algorithms, we observe that a small modification of the online covering and packing framework by Buchbinder and Naor implies a polynomial-time implementation of the primal-dual approach with separation oracles, which a priori might perform exponentially many calls to the oracle. We convert the online spanner problem into an online covering problem and complete the rounding-step analysis in a problem-specific fashion. Joint work with Elena Grigorescu and Kent Quanrud.

Polynomial Commitment schemes are a powerful cryptographic primitive that allow a sender to commit to a polynomial P, with the additional feature that the sender can open the polynomial at an evaluation point x specified by the receiver such that only P(x) is revealed. Furthermore, a proof is provided which certifies that the revealed evaluation is consistent with the committed polynomial. These commitment schemes have been a recent focus in the context of succinct (non-) interactive argument systems, where they have been used to obtain succinct arguments for NP with (nearly) optimal time tradeoffs. In this talk, I will discuss obtaining time- and space-efficient polynomial commitment schemes in the streaming model, where we assume multi-pass streaming access to the description of the polynomial we are interested in committing to. In particular, for a polynomial of description size N, we obtain a polynomial commitment scheme where the sender and receiver both run in time N polylog(N) and space polylog(N). Further, the evaluation proofs are of length polylog(N). Time permitting, I will also discuss how we use this streaming polynomial commitment scheme to obtain time- and space-efficient succinct arguments for NP. Joint work with Justin Holmgren (NTT Research), Alon Rosen (IDC Herzliya), Ron D. Rothblum (Technion), and Pratik Soni (CMU), "Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads", TCC 2020

The facility location problem is extensively studied in approximation algorithms and online algorithms, and applies to a variety of real-life situations. In the online setting of the problem, clients arrive one by one and are assigned either to an existing facility, or a newly opened facility, whose opening incurs an additional cost. Meyerson in 2001 studied the problem in the online setting, and concluded that O(log n)-competitiveness is asymptotically optimal when decisions are irrevocable. Guo et. al. in 2020 applied the concept of recourse, a measurement of how much change to the solution is made, and presented a (2.414 + eps)-approximate algorithm with O(1/eps log (1/eps) log n) amortized recourse, extending the classic 2.414-approximation for offline facility location by Charikar and Guha in 2005. Some extensions and open problems arise from this method, one of particular interest is how to apply recourse to the model in which the facilities are online instead of the clients.

We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, the edges of the input graph G = (V, E) are given as a stream e₁, …, e_m, and the algorithm is allowed to make a single pass over this stream while using O(n polylog(n)) space (m = |E| and n = |V|). If the order of edges is adversarial, a simple single-pass greedy algorithm yields a 1/2-approximation in O(n) space; achieving a better approximation in adversarial streams remains an elusive open question. A line of recent work shows that one can improve upon the 1/2-approximation if the edges of the stream arrive in a random order. The state of the art for this model is two-fold: Assadi et al. [SODA 2019] show how to compute a 2/3(∼.66)-approximate matching, but the space requirement is O(n^1.5 polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(n polylog(n)), but a worse approximation ratio of 6/11(∼.545), or 3/5(=.6) in bipartite graphs. In this paper, we present an algorithm that computes a 2/3(∼.66)-approximate matching using only O(n log(n)) space, improving upon both results above. We also note that for adversarial streams, a lower bound of Kapralov [SODA 2013] shows that any algorithm that achieves a 1-1/e(∼.63)-approximation requires (n^{1+Ω(1/log log(n))}) space. Our result for random-order streams is the first to go beyond the adversarial-order lower bound, thus establishing that computing a maximum matching is provably easier in random-order streams.<

We study sorting and searching in rounds, motivated by a cake-cutting problem. The search problem we consider is: we are given an array x=(x_1, …, x_n) and an element z promised to be in the array. We have access to an oracle that answers comparison queries: “How is z compared to x_i?”, where the answer can be “<”, “=”, or “>”. The goal is to find the location of z with success probability at least p ∈ [0,1] in at most k rounds of interaction with the oracle. The problem is called ordered or unordered search, depending on whether the array x is sorted or unsorted, respectively. For ordered search, we show the query complexity of randomized algorithms on a worst-case input is Θ(k·p·n^(1/k)) in expectation. In contrast, the query complexity of deterministic algorithms searching for a uniformly random element is Θ(k·p^(1/k) ·n^(1/k)) in expectation. The uniform distribution is the worst case for deterministic algorithms. For unordered search, the query complexity of randomized algorithms on a worst-case input is np(k+1)/2k ±1 in expectation, while the query complexity of deterministic algorithms searching for a uniformly random element is np(1−(k−1)/2k) ±1 in expectation. We also discuss the connections of these search problems to the rank query model, where the array x can be accessed via queries of the form “Is rank(x_i) ≤ y?”. Unordered search is equivalent to Select with rank queries (given q, find x_i with rank q) and ordered search to Locate with rank queries (i.e. inverse selection: given x_i, find its rank). We show an equivalence between sorting with rank queries and proportional cake cutting with contiguous pieces for any number of rounds, as well as an improved lower bound for deterministic sorting in rounds with rank queries.

We investigate the tradeoffs between fairness and efficiency when allocating indivisible items over time. Suppose T items arrive over time and must be allocated upon arrival, immediately and irrevocably, to one of n agents. Agent i assigns a value v_{it} in [0,1] to the t-th item to arrive and has an additive valuation function. We study fairness-efficiency tradeoffs in this setting and provide matching upper and lower bounds under a spectrum of progressively stronger adversaries. This is talked is based on two papers, one with Gerdus Benade, Aleksandr M. Kazachkov and Ariel D. Procaccia, and one with David Zeng.

See paper here.

A fundamental obstacle in learning information from data is the presence of nonlinear redundancies and dependencies in the statistics of the data. Information-theoretic metrics are powerful in quantifying the dependencies among the random variables. Discrete Fourier analysis on the other hand provides an essential tool to characterize the nonlinearities of functions. In this talk, I will show how the two approaches are related and can be used to remove nonlinear redundancies. In the first part of the talk, I will present a novel Fourier expansion for functions of correlated binary random variables. Starting from unsupervised learning, I will use entropy to quantify feature-redundancies and define the notion of information sufficiency. Then, based on the Fourier framework, I will present a new measure for removing redundant features. Next, in the supervised settings, I will present new theoretical results bridging the Bayesian error rate with the Fourier coefficients. Based on that, I will present a supervised algorithm for feature subset selection. In the second part of the talk, I will take a step further and discuss learning classical patterns from quantum data. In this problem, the samples are quantum states with classical labels and the predictors are quantum measurements. I will introduce a quantum counterpart of PAC as a new theoretical foundation for learning from quantum data. I will point out major difficulties arising from the quantum nature of the problem, including the no-cloning principle and measurement compatibility. Then, I will present new bounds on the quantum sample complexity of several measurement classes. I will make use of a Fourier expansion for quantum operators on qubits and present the quantum low-degree algorithm.