2022-2023
2023/5/17: Justin Gilmer, "A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture"
2023/5/17: Justin Gilmer, "A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture"
Justin Gilmer (Google)
2023/5/3: Scott Aaronson, "Certified Randomness from Quantum Supremacy"
2023/5/3: Scott Aaronson, "Certified Randomness from Quantum Supremacy"
Scott Aaronson (UT Austin / OpenAI)
2023/4/19: Michal Feldman, "Algorithmic Contract Design"
2023/4/19: Michal Feldman, "Algorithmic Contract Design"
Michal Feldman (Tel-Aviv University)
2023/4/5: Yael Tauman Kalai, "Efficient Verification of Computation on Untrusted Platforms"
2023/4/5: Yael Tauman Kalai, "Efficient Verification of Computation on Untrusted Platforms"
Yael Tauman Kalai (MSR New England)
2023/3/22: Christian Coester, "The Randomized K-Server Conjecture is False!"
2023/3/22: Christian Coester, "The Randomized K-Server Conjecture is False!"
Christian Coester (University of Oxford)
2023/3/08: Christos Tzamos, "A Strongly Polynomial Time Algorithm for Approximate Forster Transform and its Application to Halfspace Learning"
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/8: Ziv Scully, "Recent Progress in Queueing and Scheduling Theory (for a TCS Audience)"
2023/2/8: Ziv Scully, "Recent Progress in Queueing and Scheduling Theory (for a TCS Audience)"
Ziv Scully (Harvard and MIT)
2022/11/30: Nicole Wein, "Online List Labeling: Breaking the log^2 n Barrier"
2022/11/30: Nicole Wein, "Online List Labeling: Breaking the log^2 n Barrier"
Nicole Wein (DIMACS)
2022/11/09: Yaonan Jin, "First Price Auction is 1-1/e^2 Efficient"
2022/11/09: Yaonan Jin, "First Price Auction is 1-1/e^2 Efficient"
Yaonan Jin (Columbia University)
2022/10/26: Shay Moran, "A Characterization of Multiclass PAC Learning"
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"
2022/10/12: Venkatesan Guruswami, "A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes"
Venkatesan Guruswami (UC Berkeley)
2022/09/28: Joakim Blikstad, "Near Optimal Communication and Query Complexity of Bipartite Matching"
2022/09/28: Joakim Blikstad, "Near Optimal Communication and Query Complexity of Bipartite Matching"
Joakim Blikstad (KTH Royal Institute of Technology)
2022/09/14: Moses Charikar, "A Retrospective on Locality Sensitive Hashing"
2022/09/14: Moses Charikar, "A Retrospective on Locality Sensitive Hashing"
Moses Charikar (Stanford University)