In Fall 2024 the seminar was organized by Peihan Miao.

All talks were held from noon to 1PM on Wednesdays in CIT 241 unless otherwise stated.

Fall 2024 Schedule

Date	Speaker	Title	Abstract	Recording
Sept 11 (Wed)	Sebastien Roch	Some Sample Complexity Bounds in Phylogenomics	The reconstruction of species phylogenies from genomic data is a key step in modern evolutionary studies. This task is complicated by the fact that genes evolve under biological phenomena that produce discordant histories. These include hybrid speciation, horizontal gene transfer, gene duplication and loss, and incomplete lineage sorting, all of which can be modeled using random gene tree distributions building on well-studied discrete stochastic processes (branching processes, the coalescent, random rearrangements, etc.). Gene trees are in turn estimated from molecular sequences using Markov models on trees. The rigorous analysis of the resulting complex models can help guide the design of new reconstruction methods with computational and statistical guarantees. I will illustrate the challenges and opportunities in this area via some recent sample complexity bounds. No biology background will be assumed.	Talk
Sept 20 (Fri)	Shivam Nadimpalli	Gaussian Polytope Approximation	We study the approximability of high-dimensional convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution and the complexity of an approximation is the number of halfspaces used. We establish a range of upper and lower bounds both for general convex sets and for specific natural convex sets that are of particular interest. We rely on techniques from many different areas, including classical results from convex geometry, Cramér-type bounds from probability theory, and—perhaps surprisingly—a range of topics from computational complexity theory, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions. Based on joint work (https://arxiv.org/abs/2311.08575) with Anindya De and Rocco Servedio that will appear in FOCS 2024.	Talk
Sept 25 (Wed)	Kangning Wang	Metric Distortion in Social Choice	This talk will be about metric distortion in social choice. I will cover several major results (by us and others) in this area, and discuss open questions and directions. In a standard social choice scenario, voters express their preferences over candidates through votes, and then a voting rule aggregates those votes and selects one winning candidate. These votes can often be in the ranked-choice form, meaning that each voter submits her ranking of all the candidates. How efficient/effective can such voting be? In the metric distortion framework, we assume all voters and candidates reside in the same metric space, and each voter bears a cost equal to the distance between her and the elected candidate. The goal is to minimize the sum of costs over the voters. Various classical and novel voting rules can give the following guarantee: its sum of costs will be at most a constant times the true optimal sum of costs. Improving this guarantee has been the center of this research area, and this talk will review some recent progress.	Talk
Oct 2 (Wed)	Apoorv Vikram Singh	Moments, Random Walks, and Limits for Spectrum Approximation	Given random-walk access to a graph, we study lower bounds for estimating the eigenvalues of the normalized adjacency matrix of the graph in ell-1 norm. I will begin by introducing the problem of estimating eigenvalues of the graph in ell-1 norm, go over a previous technique of [Cohen-Steiner et al., KDD 2018] for estimating the eigenvalues, and then prove our lower-bound instance, which proves that the technique of [Cohen-Steiner et al., KDD 2018] is optimal. I will also present one of the consequences of our lower-bound instance proving that there are distributions on [−1, 1] that cannot be approximated to accuracy eps in Wasserstein-1 distance even if we know all of their moments to multiplicative accuracy (1 ± exp(1/eps)); this result matches an upper bound of [Kong and Valiant, Annals of Statistics 2017]. This talk is based on a joint work with Yujia Jin, Christopher Musco, and Aaron Sidford, which appeared in COLT 2023.	Talk
Oct 9 (Wed)	Zhengzhong Jin	Program Obfuscation, SNARGs, and Mathematical Logic	I will present a recent line of work that utilizes tools from mathematical logic—particularly bounded arithmetic developed by Cook, Buss, and many others—to make progress on two intriguing open questions in cryptography: (1) constructing succinct program obfuscation for Turing machines, where the obfuscated program size does not grow with an a priori upper bound on the input length, and (2) building succinct cryptographic proofs from standard assumptions that can compress the length of any NP witness. The ideas and tools may be helpful to other problems in cryptography and may also suggest new questions for proof complexity.	Talk
Oct 16 (Wed)	Nathan Klein	Ghost Value Augmentation for k-Edge-Connectivity	We show that every fractionally k-edge-connected weighted graph (i.e. every solution to the canonical k-edge-connectivity linear program) can be rounded to an integral (k-10)-edge-connected graph of no greater cost. This implies that for large constant values of k, fractional k-edge-connectivity and integral k-edge-connectivity are essentially the same. As a byproduct of this result, we show that one can produce a (k-10)-edge-connected spanning subgraph (ECSS) of cost no more than the optimal k-ECSS, complementing the existing 2-approximation. In addition, this result implies a 1+O(1/k) approximation for the k-edge-connected multi-subgraph problem (k-ECSM), resolving a conjecture of Pritchard from 2011. This is joint work with Ellis Hershkowitz and Rico Zenklusen.	Talk
Oct 23 (Wed)	Simon Meierhans	Almost-Linear Time Algorithms for Partially Dynamic Graphs	A partially dynamic graph is a graph that undergoes edge insertions or deletions, but not both. In this talk, I present a unifying framework that resolves numerous well-studied problems on such partially dynamic graphs almost-optimally. These include cycle detection, strongly connected components, s-t distances, transshipment, bipartite matching, maximum flow and minimum-cost flow. We achieve this unification by solving the partially dynamic threshold minimum-cost flow problem. In this problem, one is given a fixed demand vector and a threshold \(F\), and tasked with reporting the first time a flow of cost \(F\) exists or ceases to exist for insertions and deletions respectively. We give separate algorithms for solving this problem in the incremental and the decremental case. Both follow the L1-IPM framework introduced as part of the first almost linear time minimum-cost flow algorithm [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS’22]. For handling edge insertions, we develop new powerful data structures [Kyng-Meierhans-Probst Gutenberg, STOC’24] to solve the central min-ratio cycle problem against a general adversary [Chen-Kyng-Liu-Meierhans-Probst-Gutenberg, STOC’24]. For handling edge deletions, we take the dual perspective. This leads us to a min-ratio cut problem, which we solve by constructing a dynamic tree that approximately preserves all cuts [van den Brand-Chen-Kyng-Liu-Meierhans-Probst Gutenberg-Sachdevea, FOCS’24].	Talk
Oct 30 (Wed)	Clayton Sanford	Transformer Neural Networks Through a Communication Complexity Lens	Multi-layer transformer models form the backbone of modern deep learning, yet there is little mathematical work detailing their benefits and deficiencies as compared with other architectures. This makes it difficult to answer practical and fundamental questions about the transformer architecture: What powers are provided by increasing the depth of the model? Can alternative architectures—including state-space models like RNNs or Mamba, GNNs, or linear-time attention models—improve efficiency without sacrificing expressivity? In this talk, I’ll present a communication-based theoretical framework for understanding the representational capabilities and limitations of multi-layer transformers. Concretely, this work establishes a bidirectional relationship between the transformer architecture and the Massively Parallel Computation (MPC) model of distributed computing. This connection tightly captures the representational powers of transformers whose depth grows logarithmically in the context length and provides a separation between the transformer and alternative architectures. These results imply that parallelizability is a key property of the standard transformer that cannot be easily replicated by other architectures. I’ll also discuss empirical results that suggest that these parallelizable logarithmic-depth constructions can be found by gradient descent in an interpretable manner.	Talk
Nov 6 (Wed)	Tegan Wilson	Breaking the VLB Barrier for Oblivious Reconfigurable Networks	Valiant Load Balancing (VLB) has a long history in both the theory and practice of oblivious routing. Even after forty years, VLB continues to take center stage as a widely used — and in some settings, provably optimal — way to balance load in the network obliviously to the traffic demands. However, the ability of the network to rapidly reconfigure its interconnection topology gives rise to new possibilities. In this work we revisit the question of whether VLB remains optimal in the novel setting of reconfigurable networks. Prior work [AWSWKA’22] showed that VLB achieves the optimal tradeoff between latency and guaranteed throughput. In this work, we show that a strictly superior latency-throughput tradeoff is achievable when the throughput bound is relaxed to hold with high probability. Our results are enabled by a novel oblivious routing scheme that improves VLB by stretching routing paths the minimum possible amount — an additive stretch of 1 rather than a multiplicative stretch of 2 — yet still manages to balance load with high probability when either the traffic demand matrix or the network’s interconnection schedule are shuffled by a uniformly random permutation. This talk is based on joint work with Daniel Amir, Nitika Saran, Robert Kleinberg, Vishal Shrivastav, and Hakim Weatherspoon.	Talk
Nov 13 (Wed)	Michael P. Kim	Near-Optimal Algorithms for Omniprediction	Omnipredictors are simple prediction functions that encode loss-minimizing predictions, simultaneously for every loss function within a class of losses L. We give an oracle-efficient online learning algorithm that achieves omniprediction in Õ(T^{1/2}) regret for any class of bounded variation loss functions. Quite surprisingly, this regret bound matches the optimal regret for minimization of a single loss function (up to log factors). We leverage our result from the online setting to devise an offline learning algorithm for efficient omnipredictors, whose sample complexity scales at a near-optimal rate. Our algorithms shed light on the computational complexity of achieving omniprediction, separating the (easier) task of learning omnipredictors for convex losses from that of learning omnipredictors for proper losses. Joint work with Princewill Okoroafor and Bobby Kleinberg.	Talk
Nov 20 (Wed)	Sam Hopkins	SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More	What can efficient algorithms say about the maximum sparse singular value of a random matrix? (That is, the maximum of \|\|Mx\|\| where x is a sparse vector and M is a random matrix.) This problem turns out to be at the heart of numerous well-studied algorithmic problems: sparse principal component analysis, robust mean and covariance estimation, certification of subspace distortion, and more. I will discuss a new family of polynomial-time algorithms which can certify tighter bounds than any prior algorithm on this quantity, and their applications to improve the state of the art for the aforementioned problems. Joint work with Ilias Diakonikolas, Ankit Pensia, and Stefan Tiegel.	Talk
Nov 27 (Wed)	No seminar (Thanksgiving)
Dec 4 (Wed)	PhD students	Lightning talks by Brown PhD students