Back to Events

Seminar Series

February 06

Global Convergence of Shifted QR

Nikhil Srivastava

Part Of

4:15P
- 5:00P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-02-06 16:15:00 2024-02-06 17:00:00 America/New_York Global Convergence of Shifted QR Abstract: The Shifted QR algorithm is the most widely used algorithm since the 1960's for computing the eigenvalues and eigenvectors of a dense matrix. It is a bit like the simplex algorithm in that it is specified by a "shifting strategy" (cf. pivoting strategies for simplex). There are shifting strategies which are typically very efficient in practice and on special classes of matrices, but occasionally fail, and no strategy is known to be provably rapidly convergent on every input matrix. I will report on some recent significant progress on this question, in particular a new shifting rule which converges rapidly on a small random perturbation of every matrix. Joint work with Jorge Garza Vargas and Jess Banks. 32-G449

February 20

The Subspace Flatness Conjecture and Faster Integer Programming

Thomas Rothvoss

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-02-20 16:15:00 2024-02-20 17:15:00 America/New_York The Subspace Flatness Conjecture and Faster Integer Programming Abstract (in latex):In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$which denotes the best volume-based lower bound on the \emph{covering radius} $\mu(\Lambda,K)$ of a convexbody $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor suffices, which would matchthe lower bound from the work of Kannan and Lov\'asz.We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{3}(n)) \cdot \mu_{KL} (\Lambda,K)$. Our proof isbased on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017).Following the work of Dadush (2012, 2019), we obtain a $(\log n)^{O(n)}$-time randomized algorithm tosolve integer programs in $n$ variables.Another implication of our main result is a near-optimal \emph{flatness constant} of $O(n \log^{3}(n))$.This is joint work with Victor Reis. 32-G449

February 27

Towards a Complexity Theory for the Quantum Age

Henry Yuen
Columbia University

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-02-27 16:15:00 2024-02-27 17:15:00 America/New_York Towards a Complexity Theory for the Quantum Age Abstract: How hard is it to compress a quantum state? To fast-forward the evolution of a local Hamiltonian? To unscramble the Hawking radiation of a black hole? Traditional complexity theory -- which is centered around decision problems and tasks with classical inputs and outputs -- appears inadequate for reasoning about the complexity of such tasks involving quantum inputs and outputs.I'll discuss why we need a "fully quantum" complexity theory, and will describe some facets of such a theory. As a key illustration I'll explain how a "fully quantum" task called the Uhlmann Transformation Problem characterizes the complexity of seemingly unrelated problems, such as decoding noisy quantum channels, performing the Harlow-Hayden black hole radiation decoding task, and breaking the security of quantum bit commitment schemes. I will describe some of the many open problems and directions to explore in the world of fully quantum complexity theory.Bio: Henry Yuen is an Associate Professor of Computer Science at Columbia University. His research focuses on the interplay between quantum computing, complexity theory, cryptography, and information theory. Yuen received a BA in mathematics from the University of Southern California in 2010, and received his PhD in computer science at MIT in 2016. He is a recipient of the NSF CAREER award and a Sloan Fellowship. 32-G449

March 19

From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection

Ellen Vitercik
Stanford University

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-03-19 16:15:00 2024-03-19 17:15:00 America/New_York From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection Abstract: In clustering algorithm selection, we are given a massive dataset and must efficiently select which clustering algorithm to use. We study this problem in a semi-supervised setting, with an unknown ground-truth clustering that we can only access through expensive oracle queries. Ideally, the clustering algorithm's output will be structurally close to the ground truth. We approach this problem by introducing a notion of size generalization for clustering algorithm accuracy. We identify conditions under which we can (1) subsample the massive clustering instance, (2) evaluate a set of candidate algorithms on the smaller instance, and (3) guarantee that the algorithm with the best accuracy on the small instance will have the best accuracy on the original big instance. We verify these findings both theoretically and empirically.This is joint work with Vaggos Chatziafratis and Ishani Karmarkar. 32-G449

April 16

Succinct arguments for QMA from compiled nonlocal games

Anand Natarajan
CSAIL MIT

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-04-16 16:15:00 2024-04-16 17:15:00 America/New_York Succinct arguments for QMA from compiled nonlocal games Abstract: We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work of Mahadev (FOCS '18), Bartusek et al. (CRYPTO '22) also constructed a succinct classical argument system for QMA. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC '23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP* = RE in quantum complexity.Joint work with Tony Metger (ETH Zurich) and Tina Zhang (MIT) 32-G449

April 23

On some Recent Dynamic Graph Algorithms

Yang Liu
IAS

Part Of

4:15P
- 5:15P

Location

32-G882
Refreshments at 4:00pm
Add to Calendar 2024-04-23 16:15:00 2024-04-23 17:15:00 America/New_York On some Recent Dynamic Graph Algorithms Abstract: We discuss some recent algorithms for problems in dynamic graphs undergoing edge insertions and deletions. In the first part of the talk, we will discuss connections between the approximate bipartite matching problem in fully dynamic graphs, and versions of the online matrix-vector multiplication conjecture. These connections will lead to faster algorithms in online and offline settings, as well as some conditional lower bounds.In the second part of the talk, we will briefly discuss how interior point methods can be used to design algorithms for partially dynamic graphs: those undergoing only edge insertions (incremental) or only edge deletions (decremental). This leads to almost-optimal algorithms for problems including incremental cycle detection, and decremental s-t distance. 32-G882

May 01

Efficient Algorithms for Vector Similarities

Sandeep Silwal

Part Of

11:00A
- 1:00P

Location

Seminar Room G882 (Hewlett Room)
32-G882
Add to Calendar 2024-05-01 11:00:00 2024-05-01 13:00:00 America/New_York Efficient Algorithms for Vector Similarities Title: Efficient Algorithms for Vector SimilaritiesAbstract:A key cog in machine learning is the humble embedding: a vector representation of real world objects such as text, images, graphs, and even molecules. It is common to curate massive datasets of embeddings by inferencing on a ML model of choice. However, the sheer dataset size and large dimensionality is often *the* bottleneck in effectively leveraging and learning from this rich dataset. Inspired by this computational bottleneck in modern machine learning pipelines, we study the following question: "How can we efficiently compute on large scale high dimensional data?"In this thesis, we focus on two aspects of this question.(1) Fast local similarity computation: we give faster algorithms to compute complicated notions of similarity, such as those between collections of vectors (think optimal transport), as well as dimensionality reduction techniques which preserve similarities. In addition to computational efficiency, other resource constraints such as space and privacy are also considered.(2) Fast global similairty analysis: we study algorithms for analyzing global relationships between vectors encoded in similarity matrices. Our algorithms compute on similarity matrices, such as distance or kernel matrices, without ever initializing them, thus avoiding a quadratic time and space bottleneck.Overall, my main message is that sublinear algorithms design principles are instrumental in designing scalable algorithms for big data. For the presentation, I will only cover a subset of results in each of the categories, with a big emphasis on simplicity.Thesis Committee:Piotr Indyk (Advisor) - MITRonitt Rubinfeld - MITHuy Nguyen - Northeastern University Seminar Room G882 (Hewlett Room)

May 07

Parallel Derandomization for Chernoff-like Concentrations

Mohsen Ghaffari
CSAIL MIT

Part Of

4:15P
- 5:15P

Location

32-G882
Refreshments at 4:00pm
Add to Calendar 2024-05-07 16:15:00 2024-05-07 17:15:00 America/New_York Parallel Derandomization for Chernoff-like Concentrations Abstract: Randomized algorithms frequently use concentration results such as Chernoff and Hoeffding bounds. A longstanding challenge in parallel computing is to devise an efficient method to derandomize parallel algorithms that rely on such concentrations. Classic works of Motwani, Naor, and Naor [FOCS'89] and Berger and Rompel [FOCS'89] provide an elegant parallel derandomization method for these, via a binary search in a k-wise independent space, but with one major disadvanage: it blows up the computational work by a (large) polynomial. That is, the resulting deterministic parallel algorithm is far from work-efficiency and needs polynomial processors even to match the speed of single-processor computation. This talk overviews a duo of recent papers that provide the first nearly work-efficient parallel derandomization method for Chernoff-like concentrations.Based on joint work with Christoph Grunau and Vaclav Rozhon, which can be accessed via https://arxiv.org/abs/2311.13764 and https://arxiv.org/abs/2311.13771. 32-G882

May 14

Low-Step Multi-Commodity Flow Emulators

Thatchaphol Saranurak
University of Michigan

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-05-14 16:15:00 2024-05-14 17:15:00 America/New_York Low-Step Multi-Commodity Flow Emulators Abstract: We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.We prove the existence of low-step multi-commodity flow emulators and develop efficient algorithms to compute them. We then apply them to solve constant-approximate $k$-commodity flow in $O((m+k)^{1+\epsilon})$ time. To bypass the $O(mk)$ flow decomposition barrier, we represent our output multi-commodity flow implicitly; prior to our work, even the existence of implicit constant-approximate multi-commodity flows of size $o(mk)$ was unknown.Our results generalize to the \emph{minimum cost} setting, where each edge has an associated cost and the multi-commodity flow must satisfy a cost budget. Our algorithms are also parallel. 32-G449

May 21

Circuit Complexity from Circuit Analysis Algorithms

Ryan Williams
CSAIL MIT

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-05-21 16:15:00 2024-05-21 17:15:00 America/New_York Circuit Complexity from Circuit Analysis Algorithms Abstract: I will explain how I got into circuit complexity, and how I ended up proving theorems like "NEXP does not have small ACC circuits". (The answer may surprise you! Or maybe not.) I'll also talk about what else has been proved, building on the ideas that were introduced. 32-G449

September 17

Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry

Chara Podimata

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-09-17 16:15:00 2024-09-17 17:15:00 America/New_York Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry Abstract: In this talk I will discuss learning in principal-agent games where there is information asymmetry between what the principal and what the agent know about each other’s chosen actions. I will introduce a generalization of the standard Stackelberg Games (SGs) framework: Calibrated Stackelberg Games (CSGs). In CSGs, a principal repeatedly interacts with an agent who (contrary to standard SGs) does not have direct access to the principal’s action but instead best-responds to calibrated forecasts about it. I will show that in CSGs, the principal can achieve utility that converges to the optimum Stackelberg value of the game (i.e., the value that they could achieve had the agent known the principal’s strategy all along) both in finite and continuous settings, and that no higher utility is achievable. Finally, I will discuss a meta-question: when learning in strategic environments, can agents overcome uncertainty about their preferences to achieve outcomes they could have achieved absent any uncertainty? And can they do this solely through interactions with each other?Based on joint works with Nivasini Ananthakrishnan (UC Berkeley), Nika Haghtalab (UC Berkeley), and Kunhe Yang (UC Berkeley). 32-G449

September 24

Near Optimal Alphabet-Soundness Tradeoff PCPs

Kai Zhe Zheng
MIT Mathematics, CSAIL

Part Of

4:15P
- 5:15P

Location

32-G449
Add to Calendar 2024-09-24 16:15:00 2024-09-24 17:15:00 America/New_York Near Optimal Alphabet-Soundness Tradeoff PCPs Refreshments at 4:00 PMAbstract: We show a nearly optimal alphabet-soundness tradeoff for NP-hardness of 2-Prover-1-Round Games (2P1R). More specifically, we show that for all \eps > 0, for sufficiently large M, it is NP-hard to decide whether a 2P1R instance of alphabet size M has value nearly 1 or at most M^{-1+\eps}. 2P1R are equivalent to 2-Query PCP, and are widely used in obtaining hardness of approximation results. As such, our result implies the following: 1) hardness of approximating Quadratic Programming within a factor of nearly log(n), 2) hardness of approximating d-bounded degree 2-CSP within a factor of nearly d/2, and 3) improved hardness of approximation results for various k-vertex connectivity problems. For the first two applications, our results nearly match the performance of the best known algorithms.Joint work with Dor Minzer. 32-G449

October 08

Learning to Defer in Content Moderation: The Human-AI Interplay

Thodoris Lykouris
MIT Sloan

Part Of

4:15P
- 5:15P

Location

32-G449
Add to Calendar 2024-10-08 16:15:00 2024-10-08 17:15:00 America/New_York Learning to Defer in Content Moderation: The Human-AI Interplay Refreshments at 4:00 PMAbstract: Ensuring successful content moderation is vital for a healthy online social platform where it is necessary to responsively remove harmful posts without jeopardizing non-harmful content. Due to the high-volume nature of online posts, human-only moderation is operationally challenging, and platforms often employ a human-AI collaboration approach. A typical heuristic estimates the expected harmfulness of incoming posts and uses fixed thresholds to decide whether to remove the post and whether to send it for human review. This disregards the uncertainty in the machine learning estimation, the time-varying element of human review capacity and post arrivals, and the selective sampling in the dataset (humans only review posts filtered by the admission algorithm). We introduce a model to capture this human-AI interplay. Our algorithm observes contextual information for posts, makes classification and admission decisions, and schedules posts for human review. Only admitted posts receive human reviews on their harmfulness. These reviews help educate the machine-learning algorithms but are delayed due to congestion in the human review system. We propose a near-optimal learning algorithm that balances the classification loss from a selectively sampled dataset, the idiosyncratic loss of non-reviewed posts, and the delay loss of having congestion in the human review system. To the best of our knowledge, this is the first result for online learning in contextual queueing systems and hence our analytical framework may be of independent interest. This talk is based on joint work with Wentao Weng (Ph.D. student at MIT EECS). A preprint of the corresponding paper can be found here: https://arxiv.org/pdf/2402.12237. This work has been selected as a finalist in the 2024 INFORMS Junior Faculty Interest Group (JFIG) Paper Competition. 32-G449

November 19

Vizing’s Theorem in Near-Linear Time

Soheil Behnezhad
Northeastern University

Part Of

4:15P
- 5:15P

Location

32-G449
Add to Calendar 2024-11-19 16:15:00 2024-11-19 17:15:00 America/New_York Vizing’s Theorem in Near-Linear Time Refreshments at 4:00 PMAbstract:In his classic result, Vizing (1964) proved that any graph of maximum degree ∆ can be edge colored using at most ∆+1 different colors. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time where m and n denote the number of edges and vertices respectively. This was subsequently improved to O~(m \sqrt{n}) independently by [Arjomandi ’82; Gabow et al. ’85]. This bound remained state-of-the-art for four decades, and only recently got improved to O~(min{n^2, mn^{1/4}}) [Assadi ’24; Bhattacharya et al. ’24].In this talk, I will present a completely new approach to edge coloring that leads to the first near-linear—in fact O(m log ∆)—time algorithm for Vizing’s theorem.Based on a recent joint work with Sepehr Assadi, Sayan Bhattacharya, Martın Costa, Shay Solomon, and Tianyi Zhang. 32-G449

November 26

Recent Advances in Differential Privacy under Continual Observation

Monika Henzinger
IST Austria

Part Of

4:15P
- 5:15P

Location

32-G449
Add to Calendar 2024-11-26 16:15:00 2024-11-26 17:15:00 America/New_York Recent Advances in Differential Privacy under Continual Observation Refreshments at 4:00 PMAbstract:Differential privacy is one of the most popular definitions of privacy, being used both in research as well as in industrial applications. The multi-query setting, where many queries have to be answered over a static data set, is already well understood for many algorithmic questions. The dynamic setting, where updates to the data set are interleaved with queries over the current data set, was introduced in 2010 by Dwork, Naor, Pitassi, and Rothblum, who called it differential privacy under continual observation. While there was not much work on that model in the 2010s, it has received significant attention in recent years, partially due to its use in private machine learning. I will survey the state-of-the-art in the continual observation setting and explain its motivation as well as the main algorithmic techniques that have led to the recent advances. 32-G449

December 03

A New Approach to Optimal Spectral Gaps

Ramon van Handel
Princeton

Part Of

4:15P
- 5:15P

Location

32-124
Add to Calendar 2024-12-03 16:15:00 2024-12-03 17:15:00 America/New_York A New Approach to Optimal Spectral Gaps Refreshments at 4:00 PMAbstract:It was conjectured by Alon in the 1980s that random d-regular graphs have the largest possible spectral gap (up to negligible error) among all d-regular graphs. This conjecture was proved by Friedman in 2004 in major tour de force. In recent years, deep generalizations of Friedman's theorem, such as strong convergence of random permutation matrices due to Bordenave and Collins, have played a central role in a series of breakthrough results on random graphs, geometry, and operator algebras.In joint work with Chen, Garza-Vargas, and Tropp, we recently discovered a surprisingly simple new approach to such results that is almost entirely based on soft arguments. This approach makes it possible to address previously inaccessible questions: for example, it enables a sharp understanding of the large deviation probabilities in Friedman's theorem, and establishes optimal spectral gaps of random Schreier graphs that require many fewer random bits than ordinary random regular graphs. I will aim to explain some of these results and some intuition behind the proofs. 32-124

December 10

Coboundary Expansion Inside Chevalley Coset Complex HDXs

Ryan O'Donnell

Part Of

4:15P
- 5:15P

Location

32-G449 (Kiva/Patil)
Add to Calendar 2024-12-10 16:15:00 2024-12-10 17:15:00 America/New_York Coboundary Expansion Inside Chevalley Coset Complex HDXs Refreshments at 4:00 PMAbstract:Recent major results in property testing and PCPs were unlocked by moving to high-dimensional expanders (HDXs) constructed from C_d-type buildings, rather than the long-known A_d-type ones. At the same time, these building quotient HDXs are not as easy to understand as the more elementary (and more symmetric/explicit) coset complex HDXs constructed by Kaufman-Oppenheim [KO18] (of A-d-type) and O’Donnell-Pratt [OP22] (of Bd-, Cd-, Dd-type). Motivated by these considerations, we study the B_3-type generalization of a recent work of Kaufman-Oppenheim [KO21], which showed that the A_3-type coset complex HDXs have good 1-coboundary expansion in their links, and thus yield 2-dimensional topological expanders. The crux of Kaufman-Oppenheim’s proof of 1-coboundary expansion was: (1) identifying a group-theoretic result by Biss and Dasgupta on small presentations for the A_3-unipotent group over F_q; (2) "lifting" it to an analogous result for an A_3-unipotent group over polynomial extensions F_q[x]. For our B_3-type generalization, the analogue of (1) appears to not hold. We manage to circumvent this with a significantly more involved strategy: (1) getting a computer-assisted proof of vanishing 1-cohomology of B_3-type unipotent groups over F_5; (2) developing significant new "lifting" technology to deduce the required quantitative 1-cohomology results in B_3-type unipotent groups over F_{5^k}[x].Joint work with Noah G. Singer (Carnegie Mellon). 32-G449 (Kiva/Patil)