Seminars on Algorithms and Complexity:Archives

3 - 9 S e p t e m b e r 2 0 0 6
Wednesday September 6 12:00 noon NSH 1507	Theory Group Town Meeting	Theory Lunch
1 0 - 1 6 S e p t e m b e r 2 0 0 6
Wednesday September 13 12:00 noon NSH 1507	Mor Harchol-Balter, Carnegie Mellon University What Analytical Performance Modeling Teaches Us About Computer Systems Design (abstract)	Theory Lunch
Friday September 15 3:30 pm Wean Hall 7220	Susanne Albers, Visiting Faculty from Institut für Informatik, Universität Freiburg On Nash Equilibria for a Network Creation Game (abstract)	ALADDIN Theory Seminar
1 7 - 2 3 S e p t e m b e r 2 0 0 6
Wednesday September 20 12:00 noon NSH 1507	Ryan O'Donnell, Carnegie Mellon University 2- and 3-query property testing (abstract)	Theory Lunch
Friday September 22 3:30 pm Wean Hall 7220	Adam Klivans, University of Texas at Austin Agnostically Learning Halfspaces (abstract)	ALADDIN Theory Seminar
2 4 - 3 0 S e p t e m b e r 2 0 0 6
Wednesday September 27 12:00 noon NSH 1507	Michael Dinitz, Carnegie Mellon University Spanners with Slack (abstract)	Theory Lunch
Thursday September 28 4:30 pm PPB 300	Alan Frieze, Carnegie Mellon University Line of Sight Network (abstract)	ACO Seminar
Friday September 29 10:30 am Pitt SENSQ 5317 (map)	David S. Johnson, AT&T Labs 34 Years of Bin Packing (more info)	University of Pittsburgh Distinguished Lecturer Series
Friday September 29 3:30 pm Wean Hall 7220	Nikhil Bansal, IBM T. J. Watson Research Center Approximation Algorithms for Broadcast Scheduling (abstract)	ALADDIN Theory Seminar
1 - 7 O c t o b e r 2 0 0 6
Wednesday October 4 12:00 noon NSH 1507	Daniel Golovin, Carnegie Mellon University Quorum Placement in Networks: Minimizing Network Congestion (abstract)	Theory Lunch
Thursday October 5 4:30 pm PPB 300	Mohit Singh, Carnegie Mellon University Improved approximation ratios for traveling salesperson tours and paths in directed graphs (abstract)	ACO Seminar
Friday October 6 3:30 pm Wean Hall 7220	Gary Miller and Yiannis Koutis, Carnegie Mellon University Efficient methods for solving symmetric diagonal dominate linear systems	ALADDIN Theory Seminar
8 - 1 4 O c t o b e r 2 0 0 6
Wednesday October 11 12:00 noon NSH 1507	Viswanath Nagarajan, Carnegie Mellon University Approximating the Dial-a-Ride Problem (abstract)	Theory Lunch
Friday October 13 3:30 pm Wean Hall 7220	Santosh Vempala, Georgia Tech Dispersion of Mass and the Complexity of Randomized Algorithms (abstract)	ALADDIN Theory Seminar
1 5 - 2 1 O c t o b e r 2 0 0 6
Wednesday October 18 12:00 noon NSH 1507	Warren D. Smith, Center for Range Voting Low-Tech Secure Voting Schemes (abstract)	Theory Lunch
Thursday October 19 4:30 pm PPB 300	Vijaya Ramachandran, University of Texas at Austin The Diameter of Sparse Random Graphs (abstract)	ACO Seminar
Friday October 20	Mid-Semester Break (No Theory Seminar)	ALADDIN Theory Seminar
2 2 - 2 8 O c t o b e r 2 0 0 6
Wednesday October 25 12:00 noon NSH 1507	Todd Phillips, Carnegie Mellon University Runtime-Efficient Meshing Algorithms (abstract)	Theory Lunch
Friday October 27 3:30 pm Wean Hall 7220	Vijaya Ramachandran, University of Texas at Austin Buffer Heap: A Cache-Oblivious Priority Queue with Applications to Shortest Path Computations (abstract)	ALADDIN Theory Seminar
2 9 O c t o b e r - 4 N o v e m b e r 2 0 0 6
Wednesday November 1 12:00 noon NSH 1507	MohammadTaghi Hajiaghayi, Carnegie Mellon University Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design and Related Problems (abstract)	Theory Lunch
Thursday November 2 4:30 pm PPB 300	Anupam Gupta, Carnegie Mellon University Oblivious Network Design (abstract)	ACO Seminar
Friday November 3 3:30 pm Wean Hall 7220	Adam Meyerson, UCLA L1 Embedding for Low Bandwidth Graphs (abstract)	ALADDIN Theory Seminar
5 - 1 1 N o v e m b e r 2 0 0 6
Monday November 6 12:00 pm NSH 3305	Michael Mitzenmacher, Harvard University New Results and Open Problems for Deletion Channels and Related Synchronization Problems (abstract)	ALADDIN Theory Seminar
Wednesday November 8 12:00 noon NSH 1507	Virginia Vassilevska, Carnegie Mellon University TBA	Theory Lunch
Friday November 10 3:30 pm Wean Hall 7220	Eden Chlamtac, Princeton University New Approximation Guarantee for Chromatic Number (abstract)	ALADDIN Theory Seminar
1 2 - 1 8 N o v e m b e r 2 0 0 6
Wednesday November 15 12:00 noon NSH 1507	Don Sheehy, Carnegie Mellon University TBA	Theory Lunch
Friday November 17 3:30 pm Wean Hall 7220	Elchanan Mossel, University of California at Berkeley Broadcasting on trees: Beliefs, Evolution and Reconstruction (abstract)	ALADDIN Theory Seminar
2 6 N o v e m b e r - 2 D e ce m b e r 2 0 0 6
Thursday November 30 10:30AM CIC 410 (Intel Research) Hot Metal room	Vijaya Ramachandran, University of Texas at Austin The Cache-Oblivious Gaussian Elimination Paradigm (abstract)	Intel Research Pittsburgh Seminar
Friday December 1 3:30 pm Wean Hall 7220	Milena Mihail, Georgia Tech Algorithmic Performance in Complex Networks (abstract)	ALADDIN Theory Seminar
3 - 9 D e ce m b e r 2 0 0 6
Thursday December 7 4:30 pm PPB 300	Pall Melsted, Carnegie Mellon University Graph Limits (abstract)	ACO Seminar
1 0 - 1 6 D e ce m b e r 2 0 0 6
Thursday December 14 9:30 am - ??? NSH 3305	CSD Black Friday
Friday December 15 10:00 am - ??? NSH 3305	CSD Black Friday and Final Exams (No Theory Seminar)
1 7 - 2 3 D e ce m b e r 2 0 0 6
Friday December 22	Christmas Holiday (No Theory Seminar)
2 4 - 3 0 D e ce m b e r 2 0 0 6
Friday December 29	New Year's Eve Holiday (No Theory Seminar)
4 - 1 0 F e b r u a r y 2 0 0 7
Wednesday February 7 12:00 noon NSH 1507	Benoit Hudson, Carnegie Mellon University Three Recent Mesh Refinement Results (abstract)	Theory Lunch
1 1 - 1 7 F e b r u a r y 2 0 0 7
Wednesday February 14 12:00 noon NSH 1507	Matt Streeter, Carnegie Mellon University TBA	Theory Lunch
Friday February 16 3:30 pm Wean Hall 7220	Erik Demaine, MIT Adaptive Analysis of Algorithms (abstract)	ALADDIN Theory Seminar
1 8 - 2 4 F e b r u a r y 2 0 0 7
Wednesday February 21 12:00 noon NSH 1507	Leonid Kontorovich, Carnegie Mellon University Kernel Methods for Learning Language (abstract)	Theory Lunch
Friday February 23 3:30 pm Wean Hall 7220	Kunal Talwar, Microsoft Research The Price of Privacy and the Limits of LP Decoding (abstract)	ALADDIN Theory Seminar
2 5 F e b r u a r y - 3 M a r c h 2 0 0 7
Wednesday February 28 12:00 noon NSH 1507	Andrew Gilpin, Carnegie Mellon University Nesterov's excessive gap technique and poker (abstract)	Theory Lunch
Thursday March 1 4:30 pm PPB 300	Mohit Singh, Carnegie Mellon University Approximating Minimum Bounded Degree Spanning Trees to within one of Optimal (abstract)	ACO Seminar
Friday March 2 3:30 pm Wean Hall 7220	CANCELLED - Watch for rescheduling information Scott Aaronson, University of Waterloo The Limits of Quantum Computers (abstract)	ALADDIN Theory Seminar
4 - 1 0 M a r c h 2 0 0 7
Wednesday March 7 12:00 noon NSH 1507	Michelle Goodstein, Carnegie Mellon University A Two Player Game to Combat Web Spam (abstract)	Theory Lunch
Thursday March 8 4:30 pm PPB 300	Ryan O'Donnell, Carnegie Mellon University Understanding Parallel Repetition Requires Understanding Foams (abstract)	ACO Seminar
Friday March 9 3:30 pm Wean Hall 7220	Rocco Servedio, Columbia University Every linear threshold function has a low-weight approximator (abstract)	ALADDIN Theory Seminar
1 1 - 1 7 M a r c h 2 0 0 7
Wednesday March 14	No Theory Lunch (Spring Break)	Theory Lunch
Friday March 16	No Theory Seminar (Spring Break)	ALADDIN Theory Seminar
1 8 - 2 4 M a r c h 2 0 0 7
Monday March 19 4:30 pm WEH 7500	Dhruv MubayiUniversity of Illinois at Chicago Explicit constructions in Graph Ramsey theory	ACO Seminar
Thursday March 22 3:00 pm Wean Hall 4625	Toni Pitassi, University of Toronto Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schriver Hierarchy (abstract)	ALADDIN Theory Seminar
2 5 - 3 1 M a r c h 2 0 0 7
Friday March 30 3:30 pm Wean Hall 7220	Glencora Borradaile, Brown University An O(n log n) algorithm for maximum st-flow in a directed planar graph (abstract)	ALADDIN Theory Seminar
2 - 7 A p r i l 2 0 0 7
Thursday April 5 4:30 pm PPB 300	Oleg Pikhurko Integer Sets Having the Maximum Number of Distinct Differences	ACO Seminar
Friday April 6 3:30 pm Wean Hall 4623	Piotr Indyk, MIT Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 (abstract)	ALADDIN Theory Seminar
8 - 1 4 A p r i l 2 0 0 7
Tuesday April 10 3:30 pm Wean Hall 7500	Tom Leighton Chief Scientist, Director and Co-founder Akamai Technologies The State of Cyber Security: A Problem of National Importance (abstract)	School of Computer Science Distinguished Lecture
Wednesday April 11 12-1pm NSH 1507	Elaine Shi Multi-Dimensional Range Query over Encrypted Data	Theory Lunch
Friday April 13 3:30 pm Wean Hall 7220	Adam Smith, Penn State University Smooth Sensitivity and Sampling in Private Data Analysis (abstract)	ALADDIN Theory Seminar
1 5 - 2 1 A p r i l 2 0 0 7
Tuesday April 17 3:30 pm Wean Hall 7500	Prabhakar Raghavan Head, Yahoo! Research Web Search - From Information Retrieval to Microeconomic Modeling (abstract)	School of Computer Science Distinguished Lecture
Wednesday April 18 12:00 noon NSH 1507	Doru Balcan Characterization of Robust Linear Coding Solutions	Theory Lunch
Friday April 20 3:30 pm Wean Hall 7220	Alina Beygelzimer, IBM Watson Robust Reductions from Ranking to Classification (abstract)	ALADDIN Theory Seminar
2 3 - 2 8 A p r i l 2 0 0 7
Wednesday April 25 12:00 noon NSH 1507	Moritz Hardt, Saarland University Arithmetic Circuit Identity Testing for Sparse Polynomials (abstract)	Theory Lunch
Thursday April 26 4:30 pm PPB 300	Aaron Siegel, Institute for Advanced Study Misère quotients for impartial games	ACO Seminar
2 9 A p r i l - 5 M a y 2 0 0 7
Wednesday May 2 12:00 noon NSH 1507	Don Sheehy, Carnegie Mellon University A log-competitive algorithm for no-large-angle triangulation	Theory Lunch
Friday May 4 3:30 pm Wean Hall 7220	Balazs Szegedy, University of Toronto Testing properties of graphs and functions (abstract)	ALADDIN/Theory Seminar
Friday May 4 4:45 pm CMU Track	Fifth Annual Random Distance Run Last-minute registration from 4:00-4:30pm on the CMU Track	DEC/5 and FreeCSD
Saturday May 5 9:00 am - 5:00 pm Baker Hall A51	Workshop on Extremal Graphs and Hypergraphs	ALADDIN Workshop (Co-sponsor)
6 - 1 2 M a y 2 0 0 7
Sunday May 6 9:00 am - 5:00 pm Baker Hall A51	Workshop on Extremal Graphs and Hypergraphs	ALADDIN Workshop (Co-sponsor)
Wednesday May 9 12:00 noon NSH 1507	Christine Chung, University of Pittsburgh Stochastically stable states in load balancing and atomic congestion games (abstract)	Theory Lunch
1 3 - 1 9 M a y 2 0 0 7
Wednesday May 16 12:00 noon NSH 1507	Aaron Roth,Carnegie Mellon University Selfishness without Nash: Two Alternatives to Price of Anarchy (abstract)	Theory Lunch
Friday May 18 10:00 am NSH 3305	CSD Black Friday (No Theory Seminar)

Seminars on Algorithms and Complexity
Archives