Back to Events

Seminar Series

May 12

April 21

March 17

March 12

Interdiction problems and 2-person sequential games: beyond NP-completeness

Jim Orlin
MIT Sloan School of Management

Part Of

4:15P
- 5:15P

Location

TBD
Add to Calendar 2026-03-12 16:15:00 2026-03-12 17:15:00 America/New_York Interdiction problems and 2-person sequential games: beyond NP-completeness AbstractIn the Knapsack Problem (KP), a decision maker wants to select items of value V or more to put into a knapsack subject to a weight limit.  In the Interdiction Knapsack Problem (IKP), an adversary can block K items from being selected.  The adversary’s goal is to prevent the decision maker from achieving a value of V. The IKP is a sequential game with an initial move by the adversary followed by a move from the decision maker. The Knapsack Problem is NP-complete. The IKP is one level harder than NP-complete. We have proved a meta-theorem which establishes that the Interdiction Traveling Salesman Problem, the Interdiction Set Packing Problem, the Interdiction Set Cover Problem, and hundreds of other interdiction problems are all one level harder than NP-complete.  We have also established meta-theorems showing that hundreds of min max regret problems are one level harder than NP-complete.  We discuss our meta-theorems and relate them to the complexity of 2-person sequential games.This talk does not assume a knowledge of complexity other than an understanding of NP-completeness.This work is joint with Christoph Grüne, Berit Johannes, and Lasse Wulf.Speaker BioJames Orlin is the E. Pennell Brooks (1917) Professor of Operations Research at the MIT Sloan School.  He is best known for his research on obtaining faster algorithms for problems in network and combinatorial optimization and for his text with Ravi Ahuja and Tom Magnanti entitled Network Flows: Theory, Algorithms, and Applications. He has won various awards for his co-authored publications: including the 1993 Lanchester Prize for the best publication in O.R., the 2016 ACM SIGecom Test of Time Award, for a paper published between 10 and 25 years ago that has had “significant impact on research or applications that exemplify the interplay of economics and computation,” and the 2020 Khachyian prize for lifetime achievements in the area of optimization.  He is also a MacVicar fellow, an honor that is awarded at MIT to faculty for their “outstanding contributions to undergraduate education, and for their exceptional teaching, mentoring, and educational innovation.”  TBD

December 09

Can we speed safely?

Ronitt Rubinfeld
CSAIL, EECS

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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

Redundancy is all you need (for CSP sparsification)

Venkat Guruswami
UC Berkeley

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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

Introducing Algorithmic Thinking Theory for Foundation Models

Vincent Cohen-Addad
Google Research

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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

Nikhil Bansal
University of Michigan

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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

Rachel Zhang
CSAIL, EECS

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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

Standa Živný
University of Oxford

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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

A New Paradigm for Learning with Distribution Shift

Adam Klivans
UT Austin

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00 PM
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