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 quasipoly 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 69). 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 

Fri, Feb 10, 2023 
Guest Lecture by Sariel HarPeled on computing centerpoint of a dataset:

Paper on Computing Approximate Center Point OQ1 (Sariel): For the Center Point problem, how to improve approximation from O(1/d^2) to O(1/d^{2o(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 blackbox 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 highdimensional 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 Finegrained 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 handwritten 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 epsEmulators 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 Nearlinear Time MinCost 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 npairs Shortest Paths  Paper (FOCS'22). Lecture slides 
Wed April 26, 2023  Lecture by Ziyi Chen on SelfReducibility 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 