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 |
|
Fri, Feb 10, 2023 |
Guest Lecture by Sariel Har-Peled on computing center-point 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^{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 |