arvind@utcsri.UUCP (Arvind Gupta) (03/10/87)
From: princeton!chazelle@seismo.css.gov
Subject: Princeton Forum on Algorithms and Complexity
PRINCETON FORUM ON ALGORITHMS AND COMPLEXITY
(March 30-31, 1987)
The Department of Computer Science at Princeton University
is sponsoring an informal meeting to discuss current research
issues in the design and analysis of algorithms and data structures
and related problems in complexity theory. See program below.
The meeting will be held on March 30 and 31, 1987 at the Nassau Inn
in Princeton. There will be a $50 registration fee ($25 for students),
to help defray the costs of lunches, coffee breaks, and other social
functions.
Overnight accommodations will be available at the Nassau Inn at
discount rates. Contact the Inn directly for reservations.
Tel: (609) 921-7500.
If you are interested in attending the forum, please return the
form along with the registration fee to the address below
(checks payable to "Princeton University").
----------------------------------
PRINCETON FORUM March 30-31, 1987
Name:
Address and Affiliation:
Tel: E-mail:
For further information contact
Bernard Chazelle
Department of Computer Science
Princeton University
Princeton, NJ 08544
Phone: (609) 452-5380
CSNET: chazelle@princeton
----------------------------------
PROGRAM OF EVENTS:
Registration will be open on Sunday, March 29 from 7pm to 9pm
in the Nassau Inn.
All talks will take place in the Prince William Ballroom.
MONDAY, March 30
Morning
-------
9:00: Registration
9:45: Words of Welcome
10:00: Richard M. Karp (U.C. Berkeley),Invited Lecture
"Quick-and-Dirty Algorithms for Matching and Network Flow Problems"
10:45: R.K. Ahuja and J.B. Orlin (MIT)
"A Simple O(nm+n^2log u_max) Algorithm for Maximum Network Flows"
11:05: Coffee break
11:30: Andrew Odlyzko (AT&T, Bell Labs), Invited Lecture
"On the Complexity of the Riemann Zeta-Function"
12:30: Lunch, Nassau Inn (Senior Room)
Afternoon
---------
2:00: F.T. Leighton (MIT), Invited Lecture
"Some Computational Properties of the Hypercube"
2:45: Ken Clarkson (AT&T, Bell Labs)
"A Randomized Parallel Algorithm for Weighted Vertex Cover"
3:05: Andrew V. Goldberg (MIT)
"Implementing Parallel Graph Algorithms"
3:25: Coffee break
3:50: D. Shmoys (MIT), C. Dwork (IBM ARC), and L. Stockmeyer (IBM ARC)
"Flipping Persuasively in Constant Expected Time"
(Open Problem Session)
4:10: K. Supowit (Princeton)
"A Complexity Theory for Cellular Automata"
4:25: L.S. Heath (MIT) and S. Istrail (Wesleyan)
"Open Problems on Book-Embedding of Graphs"
4:40: Rene Schott (Universite de Nancy)
"Analysis of Dynamic Algorithms"
6:00: Reception at Prospect House (Princeton Campus)
TUESDAY, March 31
Morning
-------
9:00: V. Pan (SUNY Albany) and J. Reif (Harvard)
"Parallel Nested Dissection for Path Algebra Computations"
9:20: Endre Szemeredi (Hung. Acad. Sci., Rutgers), Invited Lecture
"Deterministic Simulations in Log-Space"
10:05: Udi Manber (Wisconsin)
"Using Mathematical Induction to Design Computer Algorithms"
10:25: Coffee break
11:00: Leslie G. Valiant (Harvard), Invited Lecture
"A Theory of Inductive Learning"
12:15: Lunch, Fine Hall (Princeton Campus)
Afternoon
---------
2:00: Gerard Cornuejols (CMU)
"General Factors in Graphs"
2:20: K.V. Palem (IBM Watson)
"On the Complexity of Precedence-Constrained Scheduling"
2:40: Jeffrey C. Lagarias (AT&T Bell Labs)
"The Geometry of Linear Programming"
3:00: Erich Kaltofen (RPI)
"Las Vegas RNC computation of the Smith normal form
of polynomial matrices"
3:20: Parting Words