Capital Area Theory Seminar: Summer/Fall 1996

The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9401842 is gratefully acknowledged.

The seminar normally meets at 4pm on Wednesday's in AVW 2120.

• Jun 12: Fan-Tao Pu (Maryland), The Plucker Coordinates of Lines in 3-Space

• Jun 26: MATH 1101 Bill Gasarch, Interactive Proof Systems

• Jul 3: AVW 3258 Randeep Bhatia, Applications of Interactive Proof Systems to Hardness of Approximations

  Jul 10: AVW 3258 Sudipto Guha, Hardness of Approximating Set-Cover

  Jul 17: AVW 3258, 3--4 PM Bill Gasarch, More on PCP stuff

  Jul 24: AVW 3258 Sudipto Guha and Samir Khuller, Approximation algorithms for connected dominating sets.

  Jul 31: AVW 3258 Robert Pless and Yoram Sussmann, Fault Tolerant K-Center Problems

  Aug 9 (Fri): AVW 2120 2-3 pm Mooly Sagiv, Chicago Parametric Shape Analysis

  Aug 14: Yossi Azar, Tel-Aviv University On-line load balancing

  Aug 21: Suleyman Sahinalp, Univ of Maryland Data Compression: An Information Theoretic Approach

  Sep 4: (Rm 1112) Teresa Przytycka, Univ of Maryland Optimal Cost Sensitive Distributed Algorithms

  Sep 11: Bill Gasarch, Univ of Maryland If you ask MORE questions then you can compute MORE stuff

  Sep 18: Lazarus, Univ of Maryland On the Khuller-Matias closest pair algorithm

  Sep 25: Rafi Hassin, Tel-Aviv University On Local Search for Weighted $k$-set Packing

  Oct 7 (MON 2pm): Sanjeev Arora, Princeton University Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems

  Oct 9: Suleyman Sahinalp, Univ of Maryland Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm

  Oct 16: Alex Chan, Univ of Maryland Lower Bounds on String Matching

  Oct 26 (SAT): Dorit Hochbaum (UC Berkeley), Mike Ball (UMCP) and David Shmoys (Cornell) FACILITY LOCATION TALKS

  Oct 30: Danny Chen, Univ of Notredame Approximate Geometric Shortest Path Queries and Related Problems

  Nov 6 (Rm 1112) : Richard Beigel, Maryland/Yale/Lehigh University Faster algorithms for 3-coloring and independent sets

  Nov 13: Joan Feigenbaum, AT&T Research Managing Trust in an Information-Labeling System

  Nov 20: Greg Frederickson, Purdue University Robustness in Combinatorial Optimization

  Dec 4: Mark Carson, Maryland Single-Source Unsplittable Flow (Kleinberg-FOCS 96)

Talks from previous semesters:

• Spring 1996
• Fall 1995

Contact: Send email to samir@cs.umd.edu for additional information. To join the theory-local mailing list, send email to smith@cs.umd.edu.