Back to Events

Seminar Series

December 05

Seth-Hardness of Coding Problems

Noah Stephens-Davidowitz
MIT CSAIL

Part Of

4:00P
- 5:00P

Location

32-D463 (Star)
Add to Calendar 2019-12-05 16:00:00 2019-12-05 17:00:00 America/New_York Seth-Hardness of Coding Problems Abstract: We show that, assuming a common conjecture in complexity theory, there are "no non-trivial algorithms" for the two most important problems in coding theory: the Nearest Codeword Problem (NCP) and the Minimum Distance Problem (MDP). Specifically, for any constant \eps > 0, there is no N^{1-\eps}-time algorithm for codes with N codewords. We also show similar results for variants of these problems, such as approximate versions, NCP withpreprocessing, etc. These results are inspired by earlier work showing similar results for the analogous lattice problems (joint works with Huck Bennett, Sasha Golovnev, and Divesh Aggarwal), but the proofs for coding problems are far simpler.Based on joint work with Vinod Vaikuntanathan, FOCS 2019 32-D463 (Star)

December 04

Discriminatory and Liberatory Algorithms: Restructuring Algorithmic “Fairness”

Manuel Sabin
Berkeley, Dpt. Computer Science

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2019-12-04 16:00:00 2019-12-04 17:00:00 America/New_York Discriminatory and Liberatory Algorithms: Restructuring Algorithmic “Fairness” Abstract: The nascent field of Algorithmic Fairness recognizes that algorithms have the potential to perpetuate and codify systemic discrimination and attempts the noble goal of defining notions of “Fairness” that will mitigate this. The past year, however, has seen many critiques of the field’s direction and methodologies, illustrating how the field itself is in danger or perpetuating and codifying systems of discrimination.This talk will review Fairness and Abstraction in Sociotechnical Systems, a work that outlines five sociotechnical “traps” that Algorithmic Fairness seems to routinely fall into. I will then present ongoing work where we introduce Discriminatory & Liberatory Algorithms (DLA): a framework to restructure the terminology, methodology, and role of Algorithmic “Fairness” through a sociotechnical lens. The merit of this will be argued via its lack of susceptibility to these five “traps.” 32-G575

November 20

The Structure of Optimal Private Tests for Simple Hypotheses

Audra McMillan
BU

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2019-11-20 16:00:00 2019-11-20 17:00:00 America/New_York The Structure of Optimal Private Tests for Simple Hypotheses Abstract: Hypothesis testing plays a central role in statistical inference, and is used in many settings where privacy concerns are paramount. In this talk we’ll address a basic question about privately testing simple hypotheses: given two distributions P and Q, and a privacy level \epsilon, how many i.i.d. samples are needed to distinguish P from Q subject to \epsilon-differential privacy, and what sort of tests have optimal sample complexity? Specifically, we'll characterize this sample complexity up to constant factors in terms of the structure of P and Q and the privacy level \epsilon, and show that this sample complexity is achieved by a certain randomized and clamped variant of the log-likelihood ratio test. This result is an analogue of the classical Neyman–Pearson lemma in the setting of private hypothesis testing. The characterization applies more generally to hypothesis tests satisfying essentially any notion of algorithmic stability, which is known to imply strong generalization bounds in adaptive data analysis, and thus our results have applications even when privacy is not a primary concern.Joint work with Clement Canonne, Gautam Kamath, Adam Smith and Jonathan Ullman. 32-G575

November 14

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space

Michael Kapralov
EPFL

Part Of

4:00P
- 5:00P

Location

32-G882
Add to Calendar 2019-11-14 16:00:00 2019-11-14 17:00:00 America/New_York Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space Abstract: In the dynamic graph streaming model, an algorithm processes, in a single pass, a stream of edge insertions and deletions to an $n$-node graph. With limited space and runtime, the goal is to output a function or approximation of the graph at the end of the stream. A central challenge in the dynamic streaming model is developing algorithms for spectral graph sparsification, which is a powerful generic approximation method.In this paper, we resolve the complexity of this problem up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses nearly linear space, processes each edge update in polylogarithmic time, and with high probability, recovers a spectral sparsifier from the sketch in nearly linear time. Prior results either achieved near optimal space, but quadratic recovery time [Kapralov et al. `14], or ran in subquadratic time, but used polynomially suboptimal space [Ahn et al `13].Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by `bucketing' vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. Our result can be viewed as giving the first efficient $\ell_2$-sparse recovery algorithm for graphs. 32-G882

November 13

Approximately counting and sampling edges uniformly, parameterized by the arboricity

Talya Eden

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2019-11-13 16:00:00 2019-11-13 17:00:00 America/New_York Approximately counting and sampling edges uniformly, parameterized by the arboricity Abstract: I will start by describing an very simple algorithm for approximating the number of edges in a graph. Then I turn to describe the problem of sampling edges from a distribution that is point-wise almost uniform.Given query access to a graph G over n vertices, m edges and a bound \alpha on the arboricity of G, both algorithms have O((n\alpha)/m) expected query complexity, so they improve on the previous O(n/\sqrt m) bound for both problems.This talk is based on joint works with Dana Ron, Will Rosenbaum and C.Seshadhri. 32-G575

November 04

Walking Randomly, Massively, and Efficiently

Piotr Sankowski
University of Warsaw

Part Of

1:30P
- 2:30P

Location

32-G882
Add to Calendar 2019-11-04 13:30:00 2019-11-04 14:30:00 America/New_York Walking Randomly, Massively, and Efficiently Abstract: We introduce an approach that allows for efficiently generating many independent random walks in big graph models, such as the Massive Parallel Computation (MPC) model. We consider the case where the space per machine is strongly sublinear in the number of vertices. In this case, many natural approaches for graph problems struggle to overcome the log(n) MPC round complexity barrier. We design a PageRank algorithm that breaks this barrier even for directed graphs.In the undirected case, we start our random walks from the stationary distribution, so we approximately know the empirical distribution of their next steps. This way we can use doubling approach to prepare continuations of sampled walks in advance. Our approach enables generating multiple random walks of length l in O(log l) rounds on MPC. Moreover, we show that under 2 Cycle conjecture this round complexity is asymptotically tight. One of the most important applications of random walks is PageRank computation. We show how to use our approach to compute approximate PageRank w.h.p. for constant damping factor:-in O(log log n) rounds on undirected graphs (with almost linear total space),-in O(log log^2 n) rounds on directed graphs  (with almost linear total space).Our algorithm for directed graphs is based on a novel idea; we define a mixture of directed and undirected versions of the graph. This allows us to start our sampling from the undirected case and then to move step by step towards the directed case. In each step, we sample slightly more walks to be able to estimate the stationary distribution for the next step.Joint work with Jakub Lacki, Slobodan Mitrovic, and Krzysztof Onak 32-G882

October 31

Mechanism Design under Interdependent Valuations

Kira Goldner

Part Of

3:00P
- 4:00P

Location

32-D463
Add to Calendar 2019-10-31 15:00:00 2019-10-31 16:00:00 America/New_York Mechanism Design under Interdependent Valuations Abstract: We study buyers with interdependent valuations: where one buyer's private information about an item impacts how much another buyer is willing to pay for it. In this setting, if a buyer misreports his own private information, he can impact not only what the auctioneer believes his own value is, but also what the auctioneer believes regarding other buyers' values as well, allowing him to essentially corrupt their values. As a result, the usual mechanism design tricks fall short, and welfare maximization is notoriously difficult. Almost all prior work in this setting requires a very strong "single-crossing" condition on the valuation functions in order to obtain any positive results. We introduce two more natural notions -- first, a relaxed, parameterized notion of single-crossing, and second, a completely unrelated notion, one of submodularity over the private information of buyers -- that each separately enable good approximation guarantees to optimal welfare. These conditions, combined with the lens of approximation, allow us to go beyond not only the restrictive single-crossing notion, but to go far beyond the single-item setting and to give positive results for even the very general setting of combinatorial auctions. Joint work with Alon Eden, Michal Feldman, Amos Fiat, and Anna Karlin. 32-D463

September 18