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 Chandra on Cuts Original paper by Panigrahi. Follow up paper1 and paper2 to show submodularity aspect. Applications: 1, 2, 3
Wed, Fri, March 1, 3, 2023 We will discuss the recent result on Shortest Path with -ve Weight Edges paper, talk by Anupam
Wed, Fri, March 8,10, 2023 Qual week! (we will go over the techniques needed for the max-flow algorithm that will be discussed the following week.)  
Wed, Fri, March 15, 17, 2023 Spring Break (Go have fun.. You deserve it)  
Wed, March 22, 2023 Lecture by Yang Liu on his max-flow result. paper, longer talk by Sushant Sachdeva
Fri, March 24, 2023 Contd.  

Tentative Topics