Algorithms and Complexity

ACO Seminar - Victor Reiner Wean Hall 8220 Anonymous (not verified) Mon, 04/06/2026 - 09:39 In Person Ehrhart theory and a q-analogue VICTOR REINER Classical Ehrhart theory begins with this fact: for a convex polytope P whose vertices lie in the integer lattice Z n , the number of lattice points in the positive integer dilates mP grows as a polynomial functio…

Operations Research Seminar - Stephen Arndt Tepper 2700 Anonymous (not verified) Fri, 04/03/2026 - 16:24 In Person Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture STEPHEN ARNDT We study algorithmic matroid intersection coloring. We give the first polynomial-time O(1)-approximation algorithm to color O(1)…

ACO Seminar - Zion Hefty Wean Hall 8220 Anonymous (not verified) Mon, 03/23/2026 - 10:19 In Person Improving R(3,k) in just two bites ZION HEFTY The Ramsey number R(t,k) is the smallest n such that any red-blue edge coloring of the n-vertex complete graph has either a t-vertex red complete subgraph or a k-vertex blue complete subgraph. We will investigate the…

ACO Seminar - Tracy Chin Wean Hall 8220 Anonymous (not verified) Mon, 03/16/2026 - 09:37 In Person Valuated Delta Matroids and Principal Minors TRACY CHIN Delta matroids are a generalization of matroids that arise naturally from combinatorial objects such as matchings, ribbon graphs, and principal minors of symmetric and skew symmetric matrices. In this talk,…

ACO Seminar - Daniel Zhu Wean 6220 Anonymous (not verified) Mon, 03/09/2026 - 16:30 In Person Schur complements for tensors and multilinear commutative rank DANIEL ZHU We show that three notions of ranks for matrices of multilinear forms are equivalent. This result generalizes a classical result of Flanders, corrects a minor hole in work of Fortin and Reutena…

Theory Lunch Seminar - Zeyu Zheng Gates Hillman 8102 Anonymous (not verified) Tue, 02/24/2026 - 10:44 In Person The generalized trifference problem ZEYU ZHENG We study the problem of finding the largest number T(n,m) of ternary vectors of length n such that for any three distinct vectors there are at least m coordinates where they pairwise differ. For m=1 , t…

ACO Seminar - Carl Schildkraut Wean Hall 8220 Anonymous (not verified) Mon, 02/23/2026 - 10:38 In Person Ramsey Cayley graphs over non-abelian groups CARL SCHILDKRAUT A conjecture of Alon states that, for some absolute constant C, every finite group G possesses a Cayley graph with clique and independence number each at most C*log|G|. Recently, Conlon, Fox, Ph…

ACO Seminar - Michael Zheng Wean Hall 8220 Anonymous (not verified) Mon, 02/16/2026 - 10:54 In Person A Lovász-Kneser theorem for triangulations MICHAEL ZHENG We show that the Kneser graph of triangulations of a convex n-gon has chromatic number n - 2. Joint work with Anton Molnar, Cosmin Pohoata, and Daniel G. Zhu. 4:00 pm → Jane Street-sponsored tea and coo…

ACO Seminar - Han Huang Wean Hall 8220 Anonymous (not verified) Mon, 02/09/2026 - 10:10 In Person Can You Recover a Manifold from a Single Random Geometric Graph? HAN HUANG Consider a manifold M that is either embedded in Euclidean space or a Riemannian manifold. We sample points X 1 ,…,X n from an unknown probability measure μ on M . We observe only a single…

ACO Seminar - Bernardo Subercaseaux Wean Hall 8220 Anonymous (not verified) Mon, 02/02/2026 - 16:38 In Person Breaking down graphs and hypergraphs into structured pieces, optimally and efficiently BERNARDO SUBERCSEAUX We will consider the problem of writing an arbitrary graph as an edge-disjoint union of complete bipartite graphs, and its natural generalizati…