List of Past CS Theory Seminars at USC

• 04/27/2011, 3:30pm, GFS 118: Yevgeniy Dodis, New York University. Leftover Hash Lemma, Revisited
• 04/07/2011, 3:30pm, SSL 150: Satyen Kale, Yahoo! Research (faculty candidate). Efficient Online Decision-Making and Applications to Semidefinite Programming
• 03/10/2011, 3:30pm, SSL 150: Shaddin Dughmi, Stanford University (faculty candidate). Randomization and Computation in Strategic Settings
• 03/01/2011, 3:30pm, SSL 150: Guy Rothblum, Princeton University (faculty candidate). Differential Privacy: Recent Developements and Future Challenges
• 02/28/2011, 3:30pm, SAL 101: Alexander Sherstov, MSR New England (faculty candidate). Limits of Communication
• 02/22/2011, 3:30pm, SSL 150: Mohit Singh, McGill Univeristy. Iterative Methods in Combinatorial Optimization
• 02/17/2011, 3:30pm, SSL 150: Virginia Vassilevska Williams, UC Berkeley (faculty candidate). Path, matrix and triangle problems -- subcubic algorithms and equivalences
• 02/08/2011, 3:30pm, SSL 150: Ankur Moitra, MIT (faculty candidate). Vertex Sparsification
• 01/20/2011, 3:30pm, SSL 150: Aleksander Madry, MIT (faculty candidate). Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms
• 01/19/2011, 10:00am, HNB Auditorium: Prof. Jenn Wortman Vaughan, UCLA. An Optimization-Based Framework for Automated Market-Making
• 12/07/2010, 3:30pm, SSL 150: Vladimir Braverman, UCLA. Space-efficient Algorithms for Data Streams
• 11/15/2010, 11:15am, KAP 140: Tim Roughgarden, Stanford University. From Bayesian to Worst-Case Optimal Auction Design
• 11/09/2010, 3:30pm, SSL 150: Shaddin Dughmi, Stanford University. How to Compute in a Selfish Society: Randomness May be the Key
• 10/07/2010, 3:30pm, SSL 150: Andrea Richa, Arizona State University. A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks
• 10/05/2010, 3:30pm, SSL 150: Maxim Sviridenko, IBM Watson. Local Search Algorithms for Submodular Maximization
• 09/14/2010, 3:30pm, SSL 150: Daniel Golovin, CalTech. Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization
• 04/23/2010, 10:00am, SSL 150: Jan Vondrak, IBM Almaden. Randomized rounding in the matroid polytope
• 04/06/2010, 4:00pm, GER Auditorium (Bekey Keynote Lecture): John Hopcroft, Cornell University. Computer science theory to support research in the information age.
• 03/30/2010, 3:30pm, SSL 150 (faculty candidate): Alexandra Kolla, IAS. New Techniques for Using and Approximating Graph Spectra.
• 02/19/2010, 10:00am, SSL 150: Frank McSherry, Microsoft Research (SVC). Differential Privacy: Theory and Practice .
• 02/16/2010, 3:30pm, SSL 150 (faculty candidate): Xi Chen, USC. From Two-Player Games to Markets: On the Computation of Equilibria .
• 12/01/2009, 4:00pm, SSL 150: Vijay Vazirani, Georgia Tech. Can Complexity Theory Ratify the "Invisible Hand of the Market".
• 10/29/2009, 4:00pm, SSL 150 (Distinguished Lecture): Fan Chung Graham, UCSD. Graph theory in the information age.
• 10/16/2009, 11:00am, PHE 333: Alex Slivkins, Microsoft Research. Learning in a Pay-per-Click Auction: Characterizing Truthful Multi-Armed Bandit Mechanisms.
• 10/06/2009, 11:00am, SGM 601: Van Vu, Rutgers. The condition number of a random matrix.
• 05/26/2009, 1:30pm, PHE 333: Vladimir Braverman, UCLA. Measuring Independence of Datasets.
• 03/06/2009, 4:00pm, SSL 150 (Distinguished Lecture): Anna Karlin, University of Washington. A Survey of Some Recent Research at the Border of Game Theory, Algorithms, and Economics.
• 02/12/2009, 4:00pm, SSL 150: Richard Cole, New York University. Explaining Market Price Discovery as an Algorithmic Process.
• 02/05/2009, 4:00pm, SSL 150: Hamid Nazerzadeh, Stanford University. The Optimization and Economic Aspects of Internet Advertising.
• 11/18/2008, 4:00pm, SSL 150: Samir Khuller, University of Maryland. On Broadcast Scheduling.
• 10/06/2008, 11:00am, ZHS 163: Alex Slivkins, Microsoft Research, SVC. Multi-Armed Bandits in Metric Spaces.
• 10/02/2008, 4:00pm, SSL 150: Shripad Thite, Caltech. Walking Your Dog in the Woods in Polynomial Time.
• 4/29/2008, 3:30pm, SSL 150: Sanjoy Dasgupta, UCSD. Random Projection Trees and Low Dimensional Manifolds.
• 4/24/2008, 3:30pm, SSL 150 (Distinguished Lecture): Avrim Blum, CMU. Semi-Supervised Learning.
• 04/22/2008, 3:30pm, SSL 150: (faculty candidate) Hoeteck Wee, Columbia University. Simple Encryption Schemes against Sophisticated Attacks.
• 03/06/2008, 3:30pm, SSL 150: (faculty candidate) Maria-Florina Balcan, CMU. A Theory of Similarity Functions for Learning and Clustering.
• 02/28/2008, 3:30pm, SSL 150: (faculty candidate) Parikshit Gopalan, University of Washington. Fitting Polynomials to Noisy Data
• 02/05/2008, 3:30pm, SSL 150: (faculty candidate) Konstantinos Daskalakis, UC Berkeley. Computing Equilibria in Games
• 01/29/2008, 3:30pm, SSL 150: (faculty candidate) Jan Vondrak, Princeton University. Approximation algorithms for combinatorial allocation problems
• 01/24/2008, 3:30pm, SSL 150: Shang-Hua Teng, Boston University. Game and Market Equilibria
• 01/17/2008, 11:00am, EEB 248: Shuchi Chawla, University of Wisconsin. Bertrand Competition in Networks
• 12/11/2007, 4:00pm, SSL 150: Maria-Florina Balcan, CMU. Mechansim Design, Machine Learning, and Pricing Problems.
• 11/06/2007, 4:00pm, SSL 150: Chris Umans, CalTech. Expanders and Extractors from Parvaresh-Vardy Codes.
• 10/16/2007, 4:00pm, SSL 150: Elliot Anshelevich, RPI. The Price of Stability for Network Design.
• 3/26/2007, 3:30pm, SSL 150: (faculty candidate) David Woodruff, MIT. Efficient and Private Distance Approximation
• 2/22/2007, 3:30pm, SSL 150: (faculty candidate) Julia Chuzhoy, IAS. Cuts and Flows in Directed Graphs
• 12/05/2006, 3:30pm, SSL 150: An Zhu, Google. Towards Achieving Anonymity
• 10/26/2006, 3:30pm, SSL 150 (Distinguished Lecture): David Johnson, AT&& Labs. Compressing Rectilinear Pictures and Minimizing Access Control Lists
• 10/05/2006, 3:30pm, SSL 150: Tanya Berger-Wolf, University of Illinois, Chicago. A Framework for Analysis of Dynamic Social Networks
• 09/19/2006, 3:30pm, SSL 150: Bobby Kleinberg, UC Berkeley/Cornell University. Competitive Collaborative Learning
• 05/02/2006, 3:00pm, SSL 150: MohammadReza Salavatipour, University of Alberta. Approximation Algorithms for Buy-at-Bulk Network Design Problems
• 03/09/2006, 3:00pm, SSL 150 (Distinguished Lecture): Éva Tardos, Cornell University. Solution Quality in Routing and Network Formation Games
• 02/24/2006, 11:00am, GFS 101: Samir Khuller, University of Maryland. Algorithms for Data Management and Migration
• 02/02/2006, 3:00pm, SSL 150: Adam Meyerson, UCLA. Randomized Online Matching
• 12/05/2005, 3:00pm, SSL 150: Bobby Kleinberg, UC Berkeley/Cornell University. Network Coding and the Capacity of Information Networks
• 05/06/2005, 2:00pm, HNB 107: Jared Saia, University of New Mexico. Choosing a random node in a large-scale network
• 12/03/2004, 11:00am, VKC 156: Frank McSherry, Microsoft Research. Data Mining via Spectral Analysis
• 11/08/2004, 11:00am, MHP 106: Venkat Guruswami, University of Washington. List Decoding of Error-Correcting Codes: Recent Progress and Challenges Ahead.
• 10/18/2004: Cris Moore, University of New Mexico and Santa Fe Institute. How Accurate are our Maps of the Internet?
• 10/06/2004, 11:00am, HNB 100: Aravind Srinivasan, University of Maryland. Massive Social Networks and Epidemiology.