Brown (Computer Science) Theory Seminar
Brown University
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 Phuoc Van Long Pham and Willem Fletcher (organizers for Fall 2026).
Relevant information for invited speakers.
| Date | Speaker | Title | Abstract | Recording |
|---|---|---|---|---|
| Sep 9 (Wed) | Rutchathon Chairattana-apirom | Recent Advances in Constructions of Pairing-Free Blind Signatures | Blind signatures, introduced by Chaum in 1983, allow a user to obtain a digital signature on a message of their choice without revealing the message to the signer. Despite decades of research, the design and analysis of blind signatures in pairing-free prime-order groups, which is one of the most fundamental cryptographic settings, are actually less understood. In this talk, I will motivate the study of blind signatures in this setting, discuss the progress made over the years, and present our recent work at CRYPTO 2026, which reduces the round complexity of pairing-free blind-signature constructions. |
|
| Sep 16 (Wed) | Vignesh Viswanathan | Towards tight approximation algorithms for maximizing Nash Welfare | My talk will be about the problem of dividing a set of indivisible items among agents with differing preferences over these items. The goal of this problem is to compute an allocation that maximizes some objective usually related to fairness and/or efficiency. I will focus on the objective of Nash welfare, which is widely regarded as an objective that (almost) perfectly balances fairness and efficiency. Despite its popularity, the approximability of max Nash welfare allocations still remains an open question with there being a gap between the best approximation algorithm and the best inapproximability result. I will discuss the following two results making progress on this open question from both directions: (1) I will present an (e^{1/e} - c)-approximation algorithm for maximizing Nash welfare for some small constant c. (2) I will show that the max Nash welfare is inapproximable by a factor of 1.076 unless the unique games conjecture is false. |
|
| Sep 23 (Wed) | Cuong Than | Beyond Worst-Case Guarantees: Light Spanners and Shallow-Light Trees | How much total edge weight is needed to preserve distances accurately? A $(1+\epsilon)$-spanner is a graph that preserves all pairwise distances within a factor of $1+\epsilon$. Classical research on light spanners has focused on worst-case bounds on their weight relative to a minimum spanning tree. Although these bounds are tight for certain inputs, they can substantially overestimate the weight needed for a particular instance. This motivates an instance-optimal perspective: can we efficiently construct a spanner whose weight is close to the minimum achievable on the given input? In this talk, I will present recent progress on this question for Euclidean spaces and planar graphs. By allowing a small increase in stretch, we obtain polynomial-time algorithms that approximate the minimum spanner weight within a constant factor on every input. The constructions use pruning techniques to eliminate redundant edges while retaining the structure needed to preserve distances. I will then discuss Euclidean shallow-light trees, which seek to preserve distances from a designated source using a tree of small total weight. In fixed-dimensional Euclidean spaces, we obtain approximation factors for weight that are polylogarithmic in $1/\epsilon$, with a relaxation of the distance guarantee. Together, these results illustrate how the structure of an input can guide the construction of light distance sketches beyond classical worst-case bounds. Based on joint work with Hung Le, Shay Solomon, Csaba D. Tóth, and Tianyi Zhang, appearing in FOCS 2024, SODA 2026, and SoCG 2026. |
|
| Sep 30 (Wed) | Hongyang Zhang | Towards understanding multi-step reasoning: Algorithmic and graph neural network perspectives | A crucial aspect of modern AI systems is their ability to perform multi-step reasoning—how do neural networks learn to decompose a complex problem into smaller subproblems? To tackle this question, in this talk, I will first present a synthetic benchmark for evaluating reasoning across twelve classical graph algorithms. In contrast to prior work that focuses on evaluating a single algorithmic reasoning task, we show that they can be learned simultaneously using graph neural networks (KDD’26). Next, I show a new stability analysis of error propagation in multi-step reasoning: How do errors occurred in earlier steps amplify into later predictions at inference time? Through this analysis, we identify a new stability measure based on spectral norms of certain Jacobian matrices, and we analyze this measure in transformer models trained to predict simple tasks like linear and quadratic functions (NeurIPS’26, to appear). Our findings shed light on several new questions concerning the expressivity of neural networks on graphs, and the stability of learning in long contexts. |
|
| Oct 7 (Wed) | Cassandra Marcussen | Quality Control Algorithms for Pattern Counting | In this talk, I will introduce “quality control problems,” which ask when it is safe to apply an average-case algorithm to a specific input. Quality control algorithms reject every input for which the algorithm is unsafe while accepting most safe inputs. I will describe quality control algorithms for assessing whether a real-valued sequence exhibits i.i.d.-like behavior, using permutation pattern counts as the measure of safety. Although worst-case algorithms for estimating permutation pattern counts require exp(k) queries, I will show that quality control can be performed with only poly(k) queries. Based on joint work with Ronitt Rubinfeld and Madhu Sudan. |
|
| Oct 14 (Wed) | Nicholas Spooner | |||
| Oct 21 (Wed) | John Kuszmaul | |||
| Oct 28 (Wed) | Dhruv Mubayi | |||
| Nov 4 (Wed) | David Heath | |||
| Nov 13 (Fri) | Tung Nguyen | |||
| Nov 18 (Wed) | Samson Zhou | |||
| Nov 25 (Wed) | Thanksgiving Break | |||
| Dec 2 (Wed) | PhD Students Talks | |||
| Dec 9 (Wed) | Niklas Dahlmeir |