CS 598 TH1: Advances in Theoretical CS

 

Lecture Schedule and Notes

Start of Student Presentations

Date Topics Reading
Tue, Jan 18, 2023 Introduction. Course overview. TFNP zoo (PLS, PPP) Scribbles
Thu, Jan 20, 2023 Continuing with TFNP: PPA, PPAD (Brouwer = SPERNER (=) PPAD) Lecture scribbles on PPA and PPAD. Slides on connections between Brouwer, Sperner, and PPAD.
Tue, Jan 25, 2023 PPAD $\cap$ PLS = CLS = Gradient Descent Slides due to Rahul Savani
Also see the paper (STOC'21 best paper award)
Fri, Jan 27, 2023 Open Problem Session: Colorful Caratheodory, Contraction Map, Simple Stochastic Games, Mean Payoff Games, Parity Games Scribbles. Paper on quasi-poly algorithm for parity games (STOC'17 best paper).
Wed, Feb 1, 2023 Interior Point Methods I Scribbles. We discussed material from notes1, Chapter 9 of Nisheeth Vishnoi's book, notes2, blog
Fri, Feb 3, 2023 Interior Point Methods II Scribbles (pages 6-9). In addition to the material from the previous lecture, Chapter 10 of Vishnoi's book. Also see this talk by Sidford on how to get to sqrt(dimension) from sqrt(# constraints).
Wed, Feb 8, 2023 Open Problems from Students
  • Anakin Dey: Natural Un-witnessable Problems (paper)
  • Eklavya Sharma: Smoothed Analysis of Binpacking (paper)
  • Zhengcheng Huang: Faster shortest path queries for planar graphs under massive parallel computing model where computation has to be done on many parallel machine each with sub-linear memory. (based on this paper appeared in SODA'23. Also if you are interested then talk to David since he seems to already have an improved result).
Fri, Feb 10, 2023

Guest Lecture by Sariel Har-Peled on computing center-point of a dataset:


A natural problem is to compute a good centerpoint of a data-set. We will present a simple algorithm for approximating the centerpoint, discuss the gap between the existential bound and the guarantee of the algorithm and discuss related problems. The talk would roughly follow this paper.

Paper on Computing Approximate Center Point

Paper on Tverberg Partition

OQ1 (Sariel): For the Center Point problem, how to improve approximation from O(1/d^2) to O(1/d^{2-o(1)})?

OQ2 (Ruta): Any smoothed complexity results possible? Or the "hard instances" are robust to noise?
Wed, Feb 15, 2023 Guest Lecture I by Alexanderos Hollender on Further Collapses in TFNP  Paper and Lecture slides.
Fri, Feb 17, 2023

Guest Lecture II by Alexanderos Hollender on Separations within TFNP

I will talk about the connections between TFNP and proof complexity and about how these connections can be used to prove black-box separations between TFNP classes.

 Paper
Wed, Feb 22, 2023 Guest lecture by Robert Andrews on Matrix Multiplication and Polynomial Identity testing.  Lecture slides. Paper appeared in FOCS 2022 (best student paper)
Fri, Feb 24, 2023 Guest Lecture by Taisuke Yasuda on high-dimensional geometric streaming paper appeared in FOCS 2022
Wed, Fri, March 1, 2023 Guest Lecture by Prof. Chandra Chekuri on Cuts Original paper by Panigrahi. Follow up paper1 and paper2 to show submodularity aspect. Applications: 1, 2, 3
Wed, March 8, 2023 Open Problem Discussion by Students  
Wed, March 10, 2023 Guest Lecture by Prof. Timothy Chan on Fine-grained Counting Lecture Scribbles wtih open problems. Based on recent work accepted to STOC'23. Here is the paper (STOC'23).
Wed, Fri, March 15, 17, 2023 Spring Break (Go have fun.. You deserve it)  
Wed, March 22, 2023 We will discuss the recent result on Shortest Path with -ve Weight Edges paper, lecture and hand-written notes by Anupam, talk by Danupon
Fri, March 24, 2023 Quantum enabled Crypto by Prof. Dakshita Khurana Lecture slides.
Student Presentations
Wed, March 29, 2023 Lecture by Han Li on Data Driven Algorithm Design Paper (STOC'21). Lecture slides
Fri, March 31, 2023 Lecture by Yuancheng Yu on Discovering faster matrix multiplication algorithms with reinforcement learning Paper (Nature'22). Lecture slides
Wed, April 5, 2023 Lecture by Eklavya Sharma on Smoothed analysis of Perceptron Paper (SODA'22). Lecture slides
Fri, April 7, 2023 Lecture by Zhencheng Huang on eps-Emulators for Planar Graphs Paper (STOC'22). Lecture slides
Wed April 12, 2023 Lecture by Elfarouk Harb on Electrical flows to Max flow Paper (STOC'22). Lecture slides
Fri April 14, 2023 Lecture by David Zheng on Near-linear Time Min-Cost Flow Paper (STOC'22). longer talk by Sushant Sachdeva
Wed April 19, 2023 Lecture by Rhea Jain on Faster Parallel Algorithm for SSSP Paper (STOC'20). Lecture slides
Fri April 21, 2023 Lecture by Anakin Dey on n-pairs Shortest Paths Paper (FOCS'22). Lecture slides
Wed April 26, 2023 Lecture by Ziyi Chen on Self-Reducibility within TFNP Paper (ITCS'23). Lecture slides
Fri April 21, 2023 Lecture by Thomas Reichel on LP in Current Matrix Multiplication Time Paper (STOC'19). Lecture slides

Tentative Topics