Theory Seminar — Fall 2022

This semester, Theory Seminar meets weekly on Mondays, 10-11 a.m. Central Time (Chicago), in Siebel 3401.

To receive updates, subscribe to the theorycs mailing list. If you are interested in giving a talk, please email Michael Forbes (miforbes [at] illinois [dot] edu).


August 29. Introductions; Timothy Chan
Real-APSP-Hardness of Triangle Finding in Sparse Graphs

September 5. Labor Day

September 12. Anamay Tengse
Natural proofs in the algebraic setting

September 19. Mik Zlatin
New and Improved Algorithms for Steiner Tree Augmentation Problems

September 26. (pre-recorded) Nutan Limaye
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

October 3. Rhea Jain
Augmentation based Approximation Algorithms for Flexible Network Design

October 10. Divyarthi Mohan
Simplicity and Optimality in Multi-Dimensional Mechanism Design

October 17. Minshen Zhu
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

October 24. Robert Andrews
On Matrix Multiplication and Polynomial Identity Testing

October 31. Eklavya Sharma
Epistemic EFX Allocations

November 7. Sorrachai Yingchareonthawornchai
Deterministic Small Vertex Connectivity in Almost Linear Time

November 14. Sanjeev Khanna
Sublinear Algorithms for Hierarchical Clustering

November 21. Fall break

November 28. William Hoza
Hitting Sets Give Two-Sided Derandomization of Small Space