The Brown Theory Seminar is a weekly seminar organized by the theory group in the Department of Computer Science at Brown University. The seminar invites external speakers to present their research on a wide range of topics in theoretical computer science.

Time and Location: All talks are held on Wednesdays noon-1pm in Lubrano (CIT 477) unless otherwise noted.

Stay Updated:

Subscribe to the theory mailing list to receive announcements about upcoming talks.
Here is a Google Calendar link with the seminar schedule.
Recordings of past talks are available on our YouTube channel.

For Speakers:

If you are interested in giving a talk, please contact Ellis Hershkowitz and Richard Huang (organizers for Fall 2025).
Relevant information for invited speakers.

Fall 2025 Schedule

Date	Speaker	Title	Abstract	Recording
Sep 19 (Fri) in CIT 368	Karthik C.S.	Recent Progress on Inapproximability of k-means and k-median in L_p-metrics	A lot of attention has been invested over the last three decades by the theory community to understand the efficiency of (even approximately) computing optimal clusters. Despite this focus, our understanding of the approximability of these clustering tasks remains poor, and our understanding of the hardness of approximation of these tasks was even worse. In this talk, I survey the recently established conceptual framework to tackle the latter issue of hardness of approximation of clustering in L_p metrics (and in particular Euclidean metric), through which we are now able to significantly improve on the inapproximability bounds established more than twenty years ago. This talk is based on a series of works with Vincent Cohen-Addad and Euiwoong Lee.	Talk
Sep 24 (Wed)	Alan Chung	Large Deviations for Outlier Eigenvalues of Gaussian Random Matrices: a Kac–Rice Approach	Random matrices play a central role in high-dimensional statistics and theoretical computer science. An important problem is to understand the large deviations of eigenvalues, which has applications in domains such as tensor PCA, community detection in networks, and planted clique problems. This work studies atypical eigenvalues of symmetric Gaussian matrices with a variance profile and additive deformations, as well as the singular values of analogous non-symmetric Gaussian matrices. Our method is also able to uncover information about the corresponding eigenvectors of atypical eigenvalues. The central technique is to apply the Kac–Rice formula to the associated quadratic forms. This is a joint work with Benjamin McKenna and Mark Sellke.	Talk
Oct 1 (Wed)	Chris Hays	Theoretical Guarantees in the Search for Less Discriminatory Algorithms	Recent scholarship has argued that firms building data-driven decision systems should search for “less discriminatory algorithms” (LDAs). That is, for a given decision problem, firms should retrain models to find models with lower disparate impact across social groups. We formalize this model retraining process as sequential samples from a distribution and analyze how a model producer (who knows little about the distribution they are sampling from and has only noisy estimates of a model’s disparate impact) should determine when to stop the retraining process. In our theoretical results, we establish statistical guarantees ensuring that the model producer does not stop training models too soon, for a given cost per training a model and value for a unit decrease in disparate impact. We then validate the method on real-world datasets.	Talk
Oct 8 (Wed)	Pachara Sawettamalya	A New Greedy Approach to Max-Flow Approximation	The maximum flow problem and its dual, the minimum s-t cut problem, are cornerstones of combinatorial optimization and graph algorithms. Despite substantial recent progress in the sequential setting, our understanding in other computational models remains much more limited. In this talk, we will discuss the minimum s-t cut problem in two settings: the two-player communication model [Yao ’79] and the cut-query model [Rubinstein–Schramm–Weinberg ’18]. Particularly, I will present a new model-independent algorithm for approximating maximum flow in undirected unweighted graphs, which can be efficiently simulated in both of these settings. When applied carefully, this yields an improved algorithm for computing an “exact” minimum s-t cut, surpassing the previous $\tilde{O}(n^{5/3})$ upper bound established independently by Rubinstein–Schramm–Weinberg (ITCS ’18) and Anand–Saranurak–Wang (SODA ’25). Based on joint work with Yonggang Jiang (MPI) and Danupon Nanongkai (MPI).	Talk
Oct 15 (Wed)	Rhea Jain	Directed Steiner Forest in Planar Digraphs	In a typical network design problem, given a graph with edge costs, the goal is to find a low-cost subgraph satisfying some connectivity requirements. Two fundamental problems in this space are Steiner Tree and Steiner Forest. While these are known to be NP-hard, they admit small constant factor approximation algorithms in undirected graphs. On the other hand, the corresponding problems on directed graphs have strong lower bounds on their approximability. In fact, no polylogarithmic approximation algorithm is known for Directed Steiner Tree, and such a result is known not to be possible for Directed Steiner Forest. Recent results demonstrate that these problems are significantly easier to solve in instances where the input directed graph is planar. Friggstad and Mousavi (ICALP ’23) obtained a simple and elegant polynomial-time O(log n)-approximation for Directed Steiner Tree in planar digraphs. Inspired by this work, we show that Directed Steiner Forest also admits a polylogarithmic approximation in planar digraphs. In this talk, I will give an overview of this algorithm and the key properties of planar graphs that are leveraged in these works. I will also highlight some related work on other network design problems in planar digraphs, including some recent extensions to length-constrained settings. This talk is based primarily on work with Chandra Chekuri published at SODA 2025.
Oct 24 (Fri)	Florentin Guth	Neural Encodings and Their Scaling Laws	Building a theory of deep learning requires identifying a small set of key quantities which characterize the behavior of the network. A natural summary statistic to consider is the dimensionality of the weights (their soft rank), which can be thought of as the number of learned “features”. I will show that this quantity admits surprisingly simple scaling laws when the number of training steps, neurons, and data samples are increased. We identify several scaling regimes characterized by different bottlenecks (capacity-limited, data-limited, etc) and distinct spectral properties. I will also discuss the behavior of the dimensionality of the overlap between a pair of networks, giving insights into memorization and generalization.	Talk
Oct 29 (Wed)	Kira Goldner	Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare	I will present work that initiates the study of multidimensional Bayesian utility maximization. In this setting, rather than using monetary payments to incentivize agents and then transferring those payments to the seller, these “payments” come in the form of “ordeals” like bureaucratic paperwork or waiting in long lines, which do not benefit anyone. This changes the mechanism designer’s objective in trading off efficiency in the allocation with inefficiency in these ordeals. In our work, we focus on the unit-demand setting where values are i.i.d. across both items and buyers. We extend the seminal results of Hartline and Roughgarden ‘08 results to the multidimensional setting, proving a tight Θ(1+logn/m) gap between optimal utility and social welfare. To do so, we develop simple, prior-independent, approximately-optimal mechanisms, targeting the simplest benchmark of optimal welfare. Joint work with Taylor Lundy (UBC).	Talk
Nov 5 (Wed)	Anupam Gupta	Beyond Adversarial Models in Online Algorithms	Consider a setting where a subset of elements of a set system arrive one by one: at each time we want to maintain a set cover (we cannot discard sets), and the goal is to do this as cheaply as possible. How do we make decisions without knowing the future? Or, jobs arrive over time and have to be assigned to machines to minimize the maximum load, and again we are faced with uncertainty: how do we decide? In this talk, I will discuss the setting where the inputs are stochastic, and show how some algorithmic+learning ideas can help us get good results. I will try to keep the discussion as self-contained as possible, and will mix in some older and some new results to give you a sense of the area.	Talk
Nov 12 (Wed)	Alex L. Wang	Subgame Perfect Algorithms for Convex Optimization	The study of convex optimization has historically been concerned with worst-case a priori convergence rates. The development of the Optimized Gradient Method (OGM), due to Drori and Teboulle, Kim and Fessler, marked a major milestone in this study, as OGM achieves the optimal worst-case convergence rate among all first-order methods in the smooth unconstrained setting. However, this notion of worst-case optimality is relatively coarse and allows OGM to perform at its worst-case rate even when better guarantees become dynamically available. This talk introduces a stronger notion of optimality for first-order methods that requires a method to give optimal dynamic guarantees that exploit “non-adversarialness” in the observed first-order information. We then give an algorithm which achieves this stronger optimality notion, the Subgame Perfect Gradient Method (SPGM), and illustrate its numerical performance. This talk is based on joint work with Benjamin Grimmer (JHU) and Kevin Shu (CalTech).	Talk
Nov 19 (Wed)	Kuikui Liu	On Zeros and Algorithms for Disordered Systems	Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statistical inference. In the “mean-field” setting, we design deterministic quasipolynomial-time algorithms for estimating the partition function to arbitrarily high accuracy in the “second moment regime”. For perhaps the most well-studied spin glass, the Sherrington Kirkpatrick model, our results achieve the conjectured optimal range of inverse temperatures. To achieve this, we study the locations of the zeros of the partition function, taking inspiration from the seminal Lee-Yang theory of phase transitions.	Talk
Nov 26 (Wed)	No seminar (Thanksgiving Break)
Dec 3 (Wed)	Jannis Blauth	Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center	One of the most elementary spreading models on graphs can be described by a fire spreading from a burning vertex in discrete time steps. At each step, all neighbors of burning vertices catch fire. A well-studied extension to model fire containment is to allow for fireproofing a number B of non-burning vertices at each step. Interestingly, basic computational questions about this model are computationally hard even on trees. One of the most prominent such examples is Resource Minimization for Fire Containment (RMFC), which asks how small B can be chosen so that a given subset of vertices will never catch fire. Despite recent progress on RMFC on trees, prior work left a significant gap in terms of its approximability. We close this gap by providing an optimal 2-approximation and an asymptotic PTAS, resolving two open questions in the literature. Both results are obtained by first designing a PTAS for a smooth variant of RMFC, which is obtained through a careful LP-guided enumeration procedure. Moreover, we show that our new techniques, with several additional ingredients, carry over to the non-uniform k-center problem (NUkC), by exploiting a link between RMFC on trees and NUkC established by Chakrabarty, Goyal, and Krishnaswamy. This leads to the first approximation algorithm for NUkC that is optimal in terms of the number of additional centers that have to be opened. This is joint work with Christian Nöbel and Rico Zenklusen..	Talk
Dec 10 (Wed)	(PhD Student Talks) Maryam Abuissa	Null Models for Hypergraphs Given Pairwise Interactions	Although hypergraphs are widely used for their ability to capture more-than-pairwise (polyadic) relationships, many applications have limited ability to directly measure polyadic interactions. Even when polyadic interactions are easy to measure, many hypergraph datasets are only published in terms of pairwise interactions. This raises the question of what information about a hypergraph can be inferred or recovered from its pairwise interactions and limited other information. I will present null models that formalize one response to this question, and MCMC algorithms to sample from them. In a more general setting where the hypergraph is fully available, these null models also provide an interesting measure of the “hyper-ness” of a hypergraph.
Dec 10 (Wed)	(PhD Student Talks) Scott Griffy	Non-Interactive Threshold Mercurial Signatures with Applications to Threshold DAC	In a mercurial signature, a signer signs a representative $m$ of an equivalence class of messages on behalf of a representative $pk$ of an equivalence class of public keys, receiving the signature $\sigma$. One can then transform into a signature $\sigma’$ on an equivalent (to $m$) message $m’$ under an equivalent (to $pk$) public key $pk’$. Mercurial signatures are helpful in constructing delegatable anonymous credentials: their privacy properties enable straightforward randomization of a credential chain, hiding the identity of each signer while preserving the authenticity of the overall credential. Unfortunately, without trusted setup, known constructions of mercurial signatures satisfy only a weak form of this privacy property. Specifically, an adversary who is responsible for a link in a delegation chain—and thus knows its corresponding secret key—will be able to recognize this link even after the chain has been randomized. To address this issue, Abe et al. (Asiacrypt 2024) proposed (interactive) threshold mercurial signatures (TMS), which remove the reliance on a single trusted signer by distributing the signing capability among multiple parties, none of whom knows the signing key. However, this contribution was far from practical, as it required the signers to interact with each other during the signing process. In this work, we define and realize non-interactive TMS, where each participant non-interactively computes its contribution to the threshold mercurial signature. Our construction also substantially reduces the overall communication complexity. It uses the mercurial signature scheme of Mir et al. (CCS 2023) as a starting point. Further, we introduce threshold delegatable anonymous credentials (TDAC) and use a non-interactive TMS to construct them.
Dec 10 (Wed)	(PhD Student Talks) Will Fletcher	Spanning Tree Embeddings Are Not Much Harder than Hierarchical Partitions	Embeddings of graph distances into trees is one of the most important techniques in algorithms. Often, applications of these embeddings require that the trees into which distances are embedded are spanning trees of the input graph. However, this requirement makes embedding much more difficult. This is largely due to the fact that embedding graph distances into hierarchical partitions of the graph is well-understood and, in turn, embedding hierarchical partitions into non-spanning trees is trivial. On the other hand, no such embedding of hierarchical partitions into spanning trees is known. In this work, we show that, generally speaking, hierarchical partitions of graphs embed into spanning trees. In particular, we show that every hierarchical partition embeds into a spanning tree with $O(1)$-distortion as long as the diameter of each level of the hierarchy increases by $\Omega(\log n)$. As an immediate consequence of our embedding, we improve the best-known approximation for universal Steiner trees (USTs) from $O(\log ^ 7 n)$ to $O(\log ^ 5 n)$. Likewise, our embedding gives a new and extremely simple probabilistic tree embedding into spanning trees with distortion $O(\log ^ 2 n)$ whose analysis is essentially the same as the classic (non-spanning) tree embedding of Bartal (FOCS’96, ESA’04). Our embeddings also give the first construction of Ramsey spanning trees from the Ramsey partitions of Mendel and Naor (FOCS’06) and the first non-trivial embeddings of hop-constrained distances into spanning trees.

Brown (Computer Science) Theory Seminar

Fall 2025 Schedule