Algorithms and Complexity Seminars
 |
Efficient Learning Algorithms under (Heavy) Contamination Thursday, April 16, 2026 - 4:00pm to 5:00pm In this talk, I will present a series of new results in supervised learning from contaminated datasets, based on a general outlier removal algorithm inspired by recent work on learning with distribution shift.
|
 |
TBA Wednesday, April 15, 2026 - 4:00pm to 5:00pm TBA |
 |
On the stability of shortest path algorithms Thursday, April 9, 2026 - 3:00pm to 4:00pm Optimization problems on random instances frequently appear in statistics and theoretical computer science, and many of them appear to be hard to solve with efficient algorithms. |
 |
Stable Open Addressing and the Curse of Reappearance Dependencies Wednesday, April 8, 2026 - 4:00pm to 5:00pm Stable hash tables—hash tables that never move existing elements—are among the simplest and most widely used hashing schemes. Two canonical examples are stable uniform probing and stable linear probing. |
 |
Half-Approximating Maximum Dicut in the Streaming Setting Wednesday, March 18, 2026 - 4:00pm to 5:00pm This talk is based on joint work with Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian, to appear at STOC'26. We study streaming algorithms for the maximum directed cut problem. |
 |
Lower Bounds for Non-adaptive Local Computation Algorithms Wednesday, March 11, 2026 - 4:00pm to 5:00pm We study non-adaptive |
 |
Ideals, Macaulay Bases, and PCPs Wednesday, March 4, 2026 - 4:00pm to 5:00pm The PCP Theorem is a central result in theoretical computer science, giving query-efficient verifiers for NP. |
 |
Upper and Lower Bounds for the Linear Ordering Principle Wednesday, February 25, 2026 - 4:00pm to 5:00pm The Linear Ordering Principle (LOP) is a total search problem that generalizes the task of finding the minimum element of a given order to settings in which the order need not be total. |
 |
Memory Reallocation with Polylogarithmic Overhead Wednesday, February 18, 2026 - 4:00pm to 5:00pm The \emph{Memory Reallocation problem} asks to dynamically maintain an assignment of given objects of various sizes to non-overlapping contiguous chunks of memory, while supporting updates (insertions/deletions) in an online fashion. |
 |
A mechanistic theory of hierarchical planning in the brain Wednesday, February 11, 2026 - 4:00pm to 5:00pm Goal-directed behavior in navigation and abstract tasks relies on hierarchical planning: long sequences are organized into subgoals and temporally extended actions. |
Pages
