Theory Seminar – Fall 2021

Theory seminar meets weekly on Mondays, 10 a.m. to 11 a.m. Central Standard/Daylight Time, via Zoom.

To receive updates, including the Zoom meeting link, subscribe to the theorycs mailing list. If you are interested in giving a talk, please email Ian Ludden (iludden2 [at] illinois [dot] edu).

Schedule

August 30. Chandra Chekuri
Densest subgraph and supermodularity

September 6. No seminar today (Labor Day)

September 13. Alexander Kelley
Improved Derandomization of Switching Lemma

September 20. Karthik Chandrasekaran
Partitioning over Submodular Structures.

September 27. Vera Traub
Better-than-2 approximation Approximations for Weighted Tree Augmentation

October 4. Young-San Lin
Online Directed Spanners and Steiner Forests

October 11. Robert Andrews
Ideals, Determinants, and Straightening

October 18. Setareh Taki
Fair Division of Indivisibles: On the Computability of Maximin Share (MMS) Allocations

October 25. Anastasios (Tasos) Sidiropoulos
Embeddings of Planar Quasimetrics into Directed L_1 and Polylogarithmic Approximation for Directed Sparsest-Cut

November 1. Nima Anari
Entropic Independence in Combinatorial Distributions

November 8. Weihang Wang
ℓ_p-norm Multiway Cut

November 15. James Hulett
SNARGs for P from Sub-exponential DDH and QR

November 22. No seminar today (Fall break)

November 29. Eklavya Sharma
Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items

December 6. David Zheng
Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

December 13.