>>Some Talks



    2026


  1. How Much Clairvoyance does a Job Need?
    Invited Talk at NYC Ops Day 2026
    Invited Talk at EaGL Theory of Computation Workshop
    [
    pptx
    ]
    (talk about our SODA 2026 and FOCS 2025 papers on robust algorithms for minimizing the total flow time)

  2. Ten Thoughts on Technical Talks
    [
    pptx
    ]
    (talk to NYU Graduate Students; you may want to check out this list as well.)

  3. Steiner Forest: A Simplified Better-Than-2 Approximation
    STOC 2026
    [
    pptx
    ]
    (Better-than-factor-of-2 for Steiner forest)

  4. Online Algorithms using Samples: A Biased Sample
    Dagstuhl Workshop on Online Algorithms beyond Competitive Analysis 2025
    STOC 2026 Workshop on Learning and Algorithms
    [
    pptx
    ]
    (Survey of some work on online algorithms which learn from a sample of the input stream given up-front.)


    5. 2025


  5. Solving Problems with Eyes Closed
    Invited Talk at StefanoFest/ALGA 2025
    [
    pptx
    ]
    (talk celebrating Stefano Leonardi's 60th birthday, discussing work in papers from 2008, and some recent developments.)

  6. Online Algorithms: Worst-Case and Beyond
    4 Lectures at the Swiss Winter School on TCS 2025
    Lecture #1: Set Cover in the Worst-Case [
    pptx
    ]
    Lecture #2: Set Cover and Network Design in Stochastic Models [part 1
    pptx
    ] [part 2
    pptx
    ]
    Lecture #3: Resource Allocation/Packing [
    pptx
    ]
    Lecture #4: Searching/Chasing Problems [
    pptx
    ]
    (broad introduction to online algorithms, both classical and modern)


    7. 2024


  7. Beyond Worst-Case Analysis for Online Algorithms
    APPROX/RANDOM 2024 Invited Talk
    [
    pptx
    ]
    (algorithms for random-order set cover and online-with-a-sample load balancing)

  8. Luca Trevisan and Sparse Cuts (with a proof of Cheeger's Inequality)
    APPROX/RANDOM 2024
    [
    pptx
    ]
    (a talk remembering Luca's contributions to finding cuts, and a randomized proof of Cheeger based on his notes.)

  9. Graph Exploration with Predictions
    Talks at Columbia and TTIC
    [
    pptx
    ]
    ("Astar-like" algorithms for graph searching when given predictions for distance to target)

  10. The Price of Explainability in Clustering
    Talk at UC San Diego and Rutgers
    [
    pptx
    ]
    (We show near-optimal bounds on the gap between explainable and general k-medians and k-means)


    11. 2019


  11. Robust Algorithms for Bandits and Secretaries
    Northwestern Quarterly Workshop
    [
    ]
    (algorithms for bandits and secretaries that allow adversarial noise)


    12. 2018


  12. Projection-based Algorithms for K-server
    Simons Reunion Workshop
    [
    ]
    (Simons semester program on Bridging Continuous and Discrete Optimization)

  13. On some Stochastic Load Balancing Problems
    Workshop on Scheduling in Data Centers
    [
    pdf
    ]
    (TTIC Summer Workshop: Data Center Scheduling from Theory to Practice)

  14. Improved Algorithms for k-cut
    Flexible Network Design workshop
    Midwest Theory Day
    [
    pptx
    ]
    (talk on approximation and exact algorithms for k-cut)

  15. Approximation Algorithms for Uncertain Environments
    SODA 2018
    [
    pptx
    ]
    (invited talk; survey on approximation algorithms for stochastic problems)


    16. 2017


  16. Sampling Algorithms for Combinatorial Pure Exploration
    Workshop on Optimization, Statistics and Uncertainty
    [
    video
    ]
    (Simons Institute semester program on Bridging Continuous and Discrete Optimization)

  17. LPs and Convex Programming Relaxations and Rounding for Stochastic Problems
    Workshop on Discrete Optimization via Continuous Relaxation
    [
    video
    ]
    (Simons Institute semester program on Bridging Continuous and Discrete Optimization)

  18. Approximation Algorithms for Stochastic Optimization
    IPCO 2017
    [
    [lec1 (pptx)], [lec2 (pptx)], [lec3 (pdf)]
    ]
    (summer school page here)

  19. Online and Dynamic Algorithms for Set Cover
    STOC 2017
    [
    pptx
    ]

  20. A Little Change will do you Good
    Workshop on Algorithms and Optimization Under Uncertainty
    [
    pptx
    ]
    (survey talk on online optimization with recourse at Shonan)

Designed by Kanat Tangwongsan, mildly altered by AG.
Last updated: 2017-05-21.