TBA
UCSD
Add to Calendar
2026-03-17 16:15:00
2026-03-17 17:15:00
America/New_York
TBA
TBA
TBD
March 17
December 09
Can we speed safely?
CSAIL, EECS
Add to Calendar
2025-12-09 16:15:00
2025-12-09 17:15:00
America/New_York
Can we speed safely?
Often, algorithmic tasks can be greatly sped up for inputs that are promised to have certain structural properties, such as inputs that are assumed to be random, or to come from restricted classes of graphs. However, in practice, we rarely know if these promises hold, and verifying them can cost more than using a worst case algorithm. This talk surveys emerging lines of work that build trustworthy fast algorithms, by pairing speedups with weaker notions of testability. Our new algorithms, which either give an answer that is certified to be correct, or flag the input as one that does not satisfy the promised conditions, have complexities that are significantly faster than that of algorithms that do not rely on promises. This talk will discuss works that are joint with Arsen Vasilyan, Talya Eden, Cassandra Marcussen, and Madhu Sudan.
TBD
October 28
Add to Calendar
2025-10-28 16:15:00
2025-10-28 17:15:00
America/New_York
Redundancy is all you need (for CSP sparsification)
Constraint Satisfaction Problems (CSPs) form a broad and central class in the theory of computation. I will describe a recent result (with J. Brakensiek, STOC ’25) showing that every CSP admits a sparsifier whose size is within polylogarithmic factors of its maximum non-redundant instance, while preserving the value of every assignment up to a small multiplicative error. A non-redundant instance is one where every constraint is essential, in the sense that some assignment satisfies exactly that constraint and no others—making such instances natural lower bounds for sparsification (for example, spanning trees are the non-redundant cut instances in graphs).Our result is established in the general setting of set families, yielding a VC-type theorem for multiplicative approximation. This unifies and extends known sparsification results for graph cuts, linear codes, and broad CSP classes. The proof hinges on an elegant entropic inequality underlying Gilmer's recent breakthrough on the union-closed sets conjecture. As a consequence of our main theorem, several results from the non-redundancy (NRD) literature immediately extend to CSP sparsification. We also obtain new results that illuminate the rich landscape of NRD itself: in recent work with Brakensiek, Jansen, Lagerkvist, and Wahlström, we show that for every rational r > 1 there exists a CSP with NRD growing as Theta(n^r). We develop an algebraic theory of conditional NRD via pattern polymorphisms, linking NRD—and hence sparsification—to Turán-type extremal problems. Revisiting Mal’tsev embeddings, the most general known route to O(n) NRD, we introduce Catalan polymorphisms, resolving several structural questions about Mal’tsev embeddings, including a predicate that admits no Abelian embedding but does embed into the non-Abelian quantum Pauli group.
TBD
October 14
Add to Calendar
2025-10-14 16:15:00
2025-10-14 17:15:00
America/New_York
Introducing Algorithmic Thinking Theory for Foundation Models
The last few months have witnessed tremendous advances on Large Language Model (LLM) reasoning capabilities with Gemini and GPT winning a gold medal at the International Mathematical Olympiad (IMO) [1] and International Collegiate Programming Contest (ICPC) [2]. Several papers have shown that inference scaling techniques significantly improve the reasoning performances of the LLM, in particular for the IMO [3]. We will discuss these results and how one can frame the problem as an optimization problem, relate it to empirical results shown in [3], and derive optimal (algorithmic) thinking strategies. We will also discuss avenues for refining the model and improving inference scaling methods.[1] https://deepmind.google/discover/blog/advanced-version-of-gemini-with-deep-think-officially-achieves-gold-medal-standard-at-the-international-mathematical-olympiad/[2] https://deepmind.google/discover/blog/gemini-achieves-gold-level-performance-at-the-international-collegiate-programming-contest-world-finals/[3] https://arxiv.org/abs/2507.15855
TBD
October 07
On Beck-Fiala and Komlós Conjectures
University of Michigan
Add to Calendar
2025-10-07 16:15:00
2025-10-07 17:15:00
America/New_York
On Beck-Fiala and Komlós Conjectures
A conjecture of Komlós states that the discrepancy of any collection of unit vectors is O(1), i.e., for any matrix A with unit columns, there is a vector x with -1,1 entries such that |Ax|_\infty = O(1). The related Beck-Fiala conjecture states that any set system with maximum degree k has discrepancy O(k^{1/2}).I will describe an O((log n)^{1/4}) bound for the Komlós problem, improving upon an O((log n)^{1/2}) bound due to Banaszczyk, using the framework of discrete Brownian motion guided by semidefinite programs. Time permitting, I will sketch how these ideas can be used to resolve the Beck-Fiala conjecture for k >=(log n)^2.
TBD
September 23
Explicit Lossless Vertex Expanders
CSAIL, EECS
Add to Calendar
2025-09-23 16:15:00
2025-09-23 17:15:00
America/New_York
Explicit Lossless Vertex Expanders
We give the first explicit construction of lossless vertex expanders. These are d-regular graphs where every small set S of vertices has (1-eps)d|S| distinct neighbors. Previously, the strongest known explicit vertex expanders were those given by Ramanujan graphs, whose spectral properties imply that every small set S of vertices has 0.5d|S| distinct neighbors.Based on joint work with Jun-Ting Hsieh, Ting-Chun Lin, Alex Lubotzky, Sidhanth Mohanty, Ryan O'Donnell, and Assaf Reiner.
TBD
September 16
Sparsification of 1-in-3-SAT
University of Oxford
Add to Calendar
2025-09-16 16:15:00
2025-09-16 17:15:00
America/New_York
Sparsification of 1-in-3-SAT
I will introduce a new notion of sparsification that doesn't drop constraints but merges variables. Using tools from additive combinatorics, I will then show that 1-in-3-SAT admits a sub-quadratic sparsifier. As an application, I will present an improved approximation algorithm for finding a linearly-ordered colouring of 3-uniform hypergraphs. Based on joint work with B. Bedert, T.-V. Nakajima, and K. Okrasa, to appear in FOCS'25.
TBD
September 09
Add to Calendar
2025-09-09 16:15:00
2025-09-09 17:15:00
America/New_York
A New Paradigm for Learning with Distribution Shift
We revisit the fundamental problem of learning with distribution shift, where a learner is given labeled samples from training distribution D, unlabeled samples from test distribution D′ and is asked to output a classifier with low test error. The standard approach in this setting is to prove a generalization bound in terms of some notion of distance between D and D′. These distances, however, are difficult to compute, and this has been the main stumbling block for efficient algorithm design over the last two decades.We sidestep this issue and define a new model called TDS learning, where a learner runs a test on the training set and is allowed to reject if this test detects distribution shift relative to a fixed output classifier. This approach leads to the first set of efficient algorithms for learning with distribution shift that do not take any assumptions on the test distribution. Finally, we discuss how our techniques have recently been used to solve longstanding problems for supervised learning with contamination.
TBD