Back to Events

Seminar Series

March 01

Efficient locally private algorithms for estimation problems

Huy Lê Nguyễn
Northeastern University

Part Of

4:00P
- 5:00P

Location

32-G575
32-G575
Add to Calendar 2023-03-01 16:00:00 2023-03-01 17:00:00 America/New_York Efficient locally private algorithms for estimation problems Abstract: In federated computation, user data is distributed over many devices which each communicate to some central server for downstream analytics and/or machine learning tasks. Already in the classical setting, there are many desiderata to be balanced in the system from accurate aggregation to low communication and fast runtime for the users and the server. Adding to the already delicate balancing, privacy concern necessitates new methods that are efficient and accurate while preserving the privacy of individual data. In this talk we will focus on two basic tasks underlying many applications: computing the histogram of user data and estimating their mean. While the problems are well-studied, a lot of recent works have been devoted to developing efficient and optimally accurate algorithms beyond asymptotic behavior. We will describe new algorithms achieving near optimal error, fast runtime, and low communication for these tasks. This is based on joint work with Hilal Asi, Vitaly Feldman, Jelani Nelson, and Kunal Talwar. 32-G575

February 22

Online Covering: Secretaries, Prophets and Universal Maps

Roie Levin
Tel Aviv University

Part Of

4:15P
- 5:15P

Location

32-G575
32-G575
Add to Calendar 2023-02-22 16:15:00 2023-02-22 17:15:00 America/New_York Online Covering: Secretaries, Prophets and Universal Maps Note the special start time (4:15pm).Abstract: We give a polynomial-time algorithm for online covering IPs with a competitive ratio of O(log mn) when the constraints are revealed in random order, essentially matching the best possible offline bound of O(log n) and circumventing the Ω(log m log n) lower bound known in adversarial order. We then use this result to give an O(log mn) competitive algorithm for the prophet version of this problem, where constraints are sampled from a sequence of known distributions (in fact, our algorithm works even when only a single sample from each of the distributions is given). Since our algorithm is universal, as a byproduct we establish that only O(n) samples are necessary to build a universal map for online covering IPs with competitive ratio O(log mn) on input sequences of length n.This talk is based on joint work with Anupam Gupta and Gregory Kehne, the first half of which appeared at FOCS 2021. 32-G575

February 16

Streaming Euclidean MST to a Constant Factor

Rajesh Jayaram
Google NYC

Part Of

4:00P
- 5:00P

Location

32-G575
32-G575
Add to Calendar 2023-02-16 16:00:00 2023-02-16 17:00:00 America/New_York Streaming Euclidean MST to a Constant Factor Abstract: We consider the problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) of an n-point set X in R^d, where the points in X are presented in an arbitrary order stream of insertions and deletions. In the streaming setting, the goal is to maintain an approximation to the MST cost in small space. In low dimensions, (1+ε) approximations are possible in sublinear (in n) space [Frahling, Indyk, Sohler, SoCG '05]. However, for high dimensional spaces the best known approximation was Õ(log n), due to [Chen, Jayaram, Levi, Waingarten, STOC '22], and prior to that it was O(log^2 n) due to [Indyk, STOC '04] and [Andoni, Indyk, Krauthgamer, SODA '08]. In this talk, we describe the first algorithm which achieves a constant factor approximation to the Euclidean MST in sublinear space. Specifically, for any ε > 0, our algorithm obtains a Õ(1/ε^2) approximation in n^{O(ε)} space. We show the approximation is tight up to a constant, by proving an Omega(sqrt{n}) space lower bound for any algorithm that beats a 1.1 approximation. Furthermore, the algorithm can be modified to give a (1+ε) approximation in O(1/ε)-passes over the stream, which separates the complexity for single vs multi-pass streaming. Joint work with Xi Chen, Vincent Cohen-Addad, Amit Levi, and Erik Waingarten (to appear in STOC '23). Full paper available at: https://arxiv.org/abs/2212.06546 32-G575

February 15

Minimum Isolating Cuts: A new tool for solving minimum cut problems

Jason Li
UC Berkeley

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2023-02-15 16:00:00 2023-02-15 17:00:00 America/New_York Minimum Isolating Cuts: A new tool for solving minimum cut problems Abstract: Minimum cut problems are among the most well-studied questions in combinatorial optimization. In this talk, I will introduce a simple but powerful new tool for solving minimum cut problems called the minimum isolating cuts. I will show how this tool can be employed to obtain faster algorithms for several fundamental min-cut problems, namely global min-cut, Steiner min-cut, and all-pairs min-cut. For these problems, the new results represent the first improvement in their runtimes in several decades.These results are in collaboration with Amir Abboud, Robert Krauthgamer, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi.