Join us this summer, June 2-5, for an exciting Summer School focused on the latest advancements in the theory of linear program solvers! Over the past few years, significant progress has been made in designing efficient linear program solvers and developing powerful new techniques, such as novel insights into interior point methods and specialized data structures to accelerate them. Our goal is to teach the algorithmic techniques that have driven these recent breakthroughs. Participants will learn about:
- Strongly Polynomial Interior Point Methods and Their Application to Generalized Flows
- Robust Interior Point Methods for Linear Programs
- Recent dynamic algorithms and data structures to accelerate IPMs
Schedule
| Start | End | Monday (June 2nd) Marcus 1117 | Tuesday (June 3rd) Marcus 1117 | Wednesday (June 4th) Klaus 1116 | Thursday (June 5th) Marcus 1117 |
|---|---|---|---|---|---|
| 9:00am | 10:30am | 9:00-9:05 Welcome Notes 9:05-9:35 Yang Liu (Path following IPM) | Jan v.d.Brand (Inverse Maintenance & Amortized Complexity) | Bento Natura (Trust Region IPM and Near-Optimal Path Following) | Yang Liu (Intro to Lee-Sidford barrier) |
| 10:30am | 11:00am | Coffee Break (coffee provided) | Coffee Break (coffee provided) | Coffee Break (coffee provided) | Coffee Break (coffee provided) |
| 11:00am | 12:30pm | Yang Liu (Stability analysis) | Bento Natura (Straight Line Complexity of the Central Path) | Yang Liu (Robust IPM) | Jan v.d.Brand (Faster Inverse Maintenance via Leverage Score Sampling) |
| 12:30pm | 2:00pm | Lunch Break | Lunch Break | Lunch Break | Lunch Break |
| 2:00pm | 3:30pm | Bento Natura (Vavasis-Ye algorithm for strongly polynomial combinatorial LP) | Jan v.d.Brand (Projection Maintenance & Matrix Multiplication Time LP Solver) | Jan v.d.Brand (Vector Maintenance for tall LP) | Bento Natura (SLC Analysis and Generalized Flows) |
| 3:30pm | 3:45pm | Break | Break | Break | |
| 3:45pm | 4:45pm | Exercise Session Sheet | Exercise Session Sheet | Exercise Session Sheet |
Location
Georgia Tech Campus,
Marcus Nanotechnology Building
Room 1117-1118
Address:
345 Ferst Dr NW
Atlanta
GA 30332
When coming from the city on 5th St, follow the street (it’ll curve a bit and change name to Ferst Drive) until you see Marcus Nanotechnology Building on your right. (Big sign in front, click here)
On Wednesday only, the summer school will be in
Klaus Advanced Computing Building
Room 1116
Address:
266 Ferst Dr NW
Atlanta
GA 30332
When coming from the city on 5th St, follow the street until you see the rainbow-colored stairs. Go up the stairs and use the main entrance on your right (Klaus Advanced Computing Building, Research Wing).
Nearby Lunch Places
- On campus, 7min walk: John Lewis Student Center
Map: https://maps.app.goo.gl/KCWww2gjPHRwH25h9
As we’re in the summer term, not all restaurants in the student center are open. You can check here which restaurants are open/available:
https://dining.gatech.edu/dining-locations/john-lewis-student-center - Near campus, 15min walk: Tech square
Map: https://maps.app.goo.gl/kWU19wDU8MnbHcwJ8
There are many options on Tech Square, but the walk is a bit longer.
Material
Speakers
- Yang P. Liu, Carnegie Mellon University, https://yangpliu.github.io/ (Speaking on Robust Interior Point Methods)
- Bento Natura, Columbia University, https://bentonatura.com/ (Speaking on Strongly Polynomial IPM and Generalized Flows)
- Jan van den Brand, Georgia Tech, https://jvdbrand.com/ (Speaking on Data Structures for IPM)
Organizers
Jan van den Brand, vdbrand@gatech.edu
Important Dates & Registration
Registration open until: Sunday, May 25, 2025 (11:59pm ET) or when full- Due date to apply for travel support: Sunday, April 6, 2025 (11:59pm ET)
- Travel support decision notification: mid-April
- Summer School: June 2-5, 2025
Registration is free but required. Registration is open until May 25th (1 week before summer school), but may close earlier due to limits on lecture hall size.
Register here: https://forms.office.com/r/06NL8kS6d2
We will offer some travel support to a limited number of students and young researchers. These are meant to roughly cover local expenses like hotel.
If you wish to apply, please submit a CV, and a brief letter outlining your (research) interests, in particular in relation to the topics of the summer school. Send the application to vdbrand@gatech.edu with subject [Summer25].
Please ask your advisor to send a brief (1 paragraph) email stating their support of the application to vdbrand@gatech.edu .