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 Richard Huang and Phuoc Pham Van Long (organizers for Spring 2026).
Relevant information for invited speakers.
| Date | Speaker | Title | Abstract | Recording |
|---|---|---|---|---|
| Feb 11 (Wed) | Zhuan Khye Koh | A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column | We give a strongly polynomial algorithm for minimum cost generalized flow, and as a consequence, for all linear programs with at most two nonzero entries per row or column. Previously, strongly polynomial algorithms were only known for the primal and dual feasibility problems. Our approach is to show that the path-following interior point method of Allamigeon et al. ‘22 terminates in a strongly polynomial number of iterations for minimum cost generalized flow. We achieve this by bounding the straight line complexity of the central path, which is the minimum number of pieces required by a piecewise affine curve to multiplicatively approximate the central path. Based on joint work with Daniel Dadush, Bento Natura, Neil Olver and László Végh. |
|
| Feb 18 (Wed) CIT 241 | Aaron (Louie) Putterman | Breaking the \(\sqrt{n}\) Barrier: New Parallel Algorithms for Finding a Matroid Basis | Over 40 years ago, Karp, Upfal, and Wigderson initiated the study of a fundamental question in parallel computation: how many adaptive rounds are required to find a basis of a matroid using only polynomially many independence queries (that is, queries that test whether a set is independent)? Their pioneering work established an upper bound of \(O(\sqrt{n})\) rounds and a lower bound of roughly \(n^{1/3}\) rounds; these bounds have remained unchanged since. In this talk, I will present recent progress on this question. We give a new parallel algorithm that, with high probability, finds a matroid basis in \(\sim O(n^{3/7})\) rounds, improving upon the classical \(O(\sqrt{n})\) bound. For the important special case of partition matroids, we obtain an optimal \(\sim O(n^{1/3})\) round algorithm, essentially settling the round complexity in this setting. Our approach introduces a new matroid decomposition technique that may be of independent interest and also yields faster parallel algorithms for the classic matroid intersection problem. This is joint work with Sanjeev Khanna and Junkai Song (NYU). |
|
| Feb 25 (Wed) | Gregory Kehne | TBD | TBD. |
|
| Mar 4 (Wed) | Alexander Poremba | TBD | TBD. |
|
| Mar 11 (Wed) | Daniel Alabi | TBD | TBD. |
|
| Mar 18 (Wed) | Alma Ghafari | TBD | TBD. |
|
| Mar 25 (Wed) | No seminar (Spring Break) | |||
| Apr 1 (Wed) | Matteo Riondato | TBD | TBD. |
|
| Apr 8 (Wed) | Miranda Christ | TBD | TBD. |
|
| Apr 15 (Wed) | Ning Luo | TBD | TBD. |
|
| Apr 22 (Wed) | PhD Student Talks |