2022-2023

2023/5/31: Paul Gölz, "News from Algorithmic Democracy: Proportional Representation for Preferences and Demographics"

2023/5/17: Justin Gilmer, "A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture"

2023/5/3: Scott Aaronson, "Certified Randomness from Quantum Supremacy"

2023/4/19: Michal Feldman, "Algorithmic Contract Design"

2023/4/5: Yael Tauman Kalai, "Efficient Verification of Computation on Untrusted Platforms"

2023/3/22: Christian Coester, "The Randomized K-Server Conjecture is False!"

2023/3/08: Christos Tzamos, "A Strongly Polynomial Time Algorithm for Approximate Forster Transform and its Application to Halfspace Learning"

2023/2/22: Jinyoung Park, "Thresholds"

2023/2/8: Ziv Scully, "Recent Progress in Queueing and Scheduling Theory (for a TCS Audience)"

2022/12/7: Ronitt Rubinfeld, "A Comedy of Errors"

2022/11/30: Nicole Wein, "Online List Labeling: Breaking the log^2 n Barrier"

2022/11/09: Yaonan Jin, "First Price Auction is 1-1/e^2 Efficient"

2022/10/26: Shay Moran, "A Characterization of Multiclass PAC Learning"

2022/10/12: Venkatesan Guruswami, "A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes"

2022/09/28: Joakim Blikstad, "Near Optimal Communication and Query Complexity of Bipartite Matching"

2022/09/14: Moses Charikar, "A Retrospective on Locality Sensitive Hashing"

2023/5/31: Paul Gölz, "News from Algorithmic Democracy: Proportional Representation for Preferences and Demographics"

Paul Gölz (Harvard)

Slides (PDF)

2023/5/17: Justin Gilmer, "A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture"

Justin Gilmer (Google)

Slides (PDF)

2023/5/3: Scott Aaronson, "Certified Randomness from Quantum Supremacy"

Scott Aaronson (UT Austin / OpenAI)

Slides (PPT)

2023/4/19: Michal Feldman, "Algorithmic Contract Design"

Michal Feldman (Tel-Aviv University)

Slides (PDF)

2023/4/5: Yael Tauman Kalai, "Efficient Verification of Computation on Untrusted Platforms"

Yael Tauman Kalai (MSR New England)

Slides (PPT)

2023/3/22: Christian Coester, "The Randomized K-Server Conjecture is False!"

Christian Coester (University of Oxford)

Slides (PDF)

2023/3/08: Christos Tzamos, "A Strongly Polynomial Time Algorithm for Approximate Forster Transform and its Application to Halfspace Learning"

Christos Tzamos (University of Athens / UW Madison)

Slides (PDF)

2023/2/22: Jinyoung Park, "Thresholds"

Jinyoung Park (NYU/Courant Institute)

Slides (PDF)

2023/2/8: Ziv Scully, "Recent Progress in Queueing and Scheduling Theory (for a TCS Audience)"

Ziv Scully (Harvard and MIT)

Slides (PDF)

2022/12/7: Ronitt Rubinfeld, "A Comedy of Errors"

Ronitt Rubinfeld (MIT)

Slides (PDF)

2022/11/30: Nicole Wein, "Online List Labeling: Breaking the log^2 n Barrier"

Nicole Wein (DIMACS)

Slides (PDF)

2022/11/09: Yaonan Jin, "First Price Auction is 1-1/e^2 Efficient"

Yaonan Jin (Columbia University)

Slides (PDF)

2022/10/26: Shay Moran, "A Characterization of Multiclass PAC Learning"

Shay Moran (Technion and Google Research)

2022/10/12: Venkatesan Guruswami, "A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes"

Venkatesan Guruswami (UC Berkeley)

Slides (PDF)

2022/09/28: Joakim Blikstad, "Near Optimal Communication and Query Complexity of Bipartite Matching"

Joakim Blikstad (KTH Royal Institute of Technology)

Slides (PDF)

2022/09/14: Moses Charikar, "A Retrospective on Locality Sensitive Hashing"

Moses Charikar (Stanford University)