arvind@utcsri.UUCP (09/21/87)
Date: 18 Sep 1987 00:16:40-EDT (Friday)
From: Ashok Chandra <ASHOK@ibm.com>
Subject: FOCS 1987 registration and program
FOCS 1987
28th Annual Symposium on Foundations of Computer Science
Los Angeles, California
October 12-14, 1987
REGISTRATION
Use this form or a facsimile to preregister. Advanced registration
material should be sent postmarked by Wednesday, September 23, 1987.
Please make checks payable to "Foundations of Computer Science 1987".
Mail check and completed form to:
Seymour Ginsburg
Foundations of Computer Science 1987
Computer Science Department
University of Southern California
Los Angeles, CA 90089-0782
(Telephone: 213-743-2068)
Mailed by After
Fees(check one) Sept 23, 1987 Sept 23, 1987
Member of IEEE Computer
Society or SIGACT $165 $220
Nonmembers $220 $290
Author or Program Committee
Member $165 $220
Full-time students $50 $60
Name _______________________________________________________
Affiliation ________________________________________________
Address ____________________________________________________
City _______________________ State ________________________
Country _________________________________ Zip ______________
Tel ______________________ Elec. mail _____________________
Dietary restriction: Kosher ___ Vegetarian ___
Request for refund will be honored until October 5, 1987.
HOTEL RESERVATION FORM
Mail to:
FOCS Symposium
Reservations Department
Marina Beach Hotel
4100 Admiralty Way
Marina Del Rey, CA. 90292
(Telephone, Inside Calif: 800-8-MARINA; Outside Calif: 800-882-4000)
Please reserve a room for me at the Foundations of Computer Science
Symposium, October 11-14, 1987.
Single $85 per day
Double(twin) $85 per day
Triple $100 per day
(plus 10% occupancy tax)
Arrival date and time _______________________________________
Departure date ______________________________________________
Please send confirmation to:
Mr./Ms. ________________________________________________________
(Please print full name)
Address ________________________________________________________
City _____________________ State ________________ Zip __________
Country ________________________________________________________
To avoid duplication of reservations, please submit only one form
when sharing rooms.
Names of the others sharing the room:
_________________________________________________________________
_________________________________________________________________
Please be sure your reservation reaches the hotel (or call the
toll-free number) by Sep 21 to ensure your accommodations.
Payment of first night's lodging is required as a deposit - credit
card authorizations will be accepted over the telephone. Refund due
to cancellation will be honored until 72 hours prior to arrival time.
Indicate method of payment:
First night's deposit enclosed ___________
Credit card _______________ #_________________ Exp _______________
Signature ___________________________________________________
Print Name __________________________________________________
CONFERENCE INFORMATION
LOCATION
The conference will be at the Marina Beach Hotel, 4100 Admiralty Way,
Marina Del Rey, CA. 90292. (Telephone, Inside Calif: 800-8-MARINA; Outside
Calif: 800-882-4000.) All technical sessions will be held in the Grand
Ballroom of that hotel.
A block of 300 rooms has been reserved (until Monday, Sept 21) at the
Marina Beach Hotel. 50 additional rooms have been reserved as backup at the
Marina International Hotel (one block away). The price for rooms at both
hotels are the same, namely $85 per night for one or two people, and
$100 for three. Please make reservations directly with the Marina Beach
Hotel.
TRANSPORTATION:
The Marina Beach Hotel is approximately 6 miles north of the Los Angeles
International Airport, in the fashionable Marina Del Rey area of Los
Angeles. Complementary transportation is available for individuals
arriving at the airport; use the courtesy phone in the baggage claim
area to call the hotel. Taxi fare from the airport is about $13. Those
coming by car should take Lincoln Blvd to Bali Way, go left one block,
and then right on Admiralty Way for about a mile to the hotel.
CLIMATE: Weather during the middle of October is usually mild, with just
a slight chance of rain. Daytime temperatures range between 60 degrees F
and 75 degrees F, with slightly cooler evenings.
THINGS TO DO: The marina is the world's largest man-made small craft harbor.
Activities available nearby include sailing, harbor cruises, fishing, and
jogging. A variety of shops and restaurants are located within a mile of the
hotel.
REGISTRATION: Registration for the conference will be located in the foyer
of the hotel, and will be open Sunday (5:00 p.m. - 10:00 p.m.), Monday (8:30
a.m. - 5:00 p.m.), and Tuesday (9:00 a.m. - 12:00 p.m.). Fees are listed
elsewhere in this brochure. The regular registration fee includes technical
sessions, a copy of the proceedings, the Sunday reception, three luncheons,
and the Tuesday evening banquet. The student registration fee does not
include the banquet. Students should bring evidence of student status to the
registration desk.
RECEPTION: A reception will be held Sunday, October 11, from 8:00 p.m. to
11:00 p.m. in the Grand Ballroom of the hotel.
BUSINESS MEETING: There will be a business meeting on Monday evening from
9 p.m. to 10:30 p.m. in the Grand Ballroom. All interested registrants are
invited.
BANQUET: The Banquet will be on Tuesday evening in the Grand Ballroom.
Doors will open at 7:00 p.m.
PROCEEDINGS: A limited number of additional copies of the Symposium
Proceedings will be available for purchase at the registration desk.
ACKNOWLEDGMENTS: Student meals were made possible by a contribution from
the industrial affiliates of SIGACT and TC-MFC.
MACHTEY AWARD: The Machtey Award is presented for the most outstanding
paper written by a student or students, as judged by the program committee.
It includes a grant to help defray authors' expenses in attending the
FOCS Symposium. Please consider a donation to the Machtey Award Fund to
sustain this tradition. All donations should be made payable to the Machtey
Award Fund on a separate check and sent with the regular registration items.
CONFERENCE CREDITS
LOCAL ARRANGEMENTS CHAIR
Seymour Ginsburg (with the assistance of Ming-Deh Huang)
Computer Science Department
University of Southern California
Los Angeles, CA. 90089-0782
(Telephone: 213-743-2068)
CONFERENCE CHAIR
Ashok K Chandra
IBM T.J. Watson Research Center
P.O.Box 218
Yorktown Heights,NY 10598
CONFERENCE SECRETARY
David W Bray
Clarkson College
Educational Computing
Potsdam, N.Y. 13676
SYMPOSIUM COORDINATOR
John C Cherniavsky
Computer Science Department
Georgetown University
Washington, D.C. 20057
PROGRAM COMMITTEE CHAIR
Tom Leighton
Department of Mathematics
Massachussetts Institute of Technology
Cambridge, MA 02139
PROGRAM COMMITTEE
Laszlo Babai Paris Kanellakis
Michael Ben-Or Rao Kosaraju
Michael Fischer Tom Leighton
Shafi Goldwasser Michael Paterson
Leonidas Guibas Robert Tarjan
Joseph Halpern Uzi Vishkin
PROGRAM FOR FOCS '87
MONDAY, OCTOBER 12
Session 1. Chair: Leonidas Guibas
8:30 Polytope range searching and integral geometry
B. Chazelle, Princeton U.
8:50 An output sensitive algorithm for computing visibility graphs
S. Ghosh, U. Maryland
D. Mount, U. Maryland
9:10 Delaunay graphs are almost as good as complete graphs
D. Dobkin, Princeton U.
S. Friedman, Princeton U.
K. Supowit, Princeton U.
9:30 On the lower envelope of bivariate functions and its applications
H. Edelsbrunner, U. Illinois at Urbana
J. Pach, Hungarian Academy of Sciences
J. Schwartz, N.Y.U.
M. Sharir, Tel Aviv U.
9:50 Break
Session 2. Chair: Michael Paterson
10:20 A new algebraic method for robot motion planning and real geometry
J. Canny, M.I.T.
10:40 New lower bound techniques for robot motion planning problems
J. Canny, M.I.T.
J. Reif, Duke U.
11:00 Learning one-counter languages in polynomial time
P. Berman, Penn. State U.
R. Roos, Penn. State U.
11:20 Learning quickly when irrelevant attributes abound: a new linear-
threshold algorithm
N. Littlestone, U.C. Santa Cruz
11:40 Diversity-based inference of finite automata
R. Rivest, M.I.T.
R. Schapire, M.I.T.
12:00 Lunch
Session 3. Chair: Michael Fischer
2:00 Incomparability in parallel computation
V. Grolmusz, U. Chicago and Eotvos U.
P. Ragde, U. Toronto
2:20 Threshold circuits of bounded depth
A. Hajnal, U. Illinois at Chicago and Hungarian Academy of Sciences
W. Maass, U. Illinois at Chicago
P. Pudlak, U. Illinois at Chicago and Czechoslovakian Acad. Sciences
M. Szegedy, U. Chicago
G. Turan, U. Illinois at Chicago and Hungarian Academy of Sciences
3:00 Complete and incomplete randomized NP problems
Y. Gurevich, U. Michigan
3:20 Generic oracles and oracle classes
M. Blum, U.C. Berkeley
R. Impagliazzo, U.C. Berkeley
3:40 Break
Session 4. Chair: Michael Ben-Or
4:10 Polynomial decomposition algorithms
D. Kozen, Cornell U.
S. Landau, Wesleyan U.
J. von zur Gathen, U. Toronto
4:30 Factoring polynomials over finite fields
L. Ronyai, Hungarian Academy of Sciences and U. Chicago
4:50 Multiplicative complexity of polynomial multiplication over finite
fields
M. Kaminski, Technion
N. Bshouty, Technion
5:10 The multiplicative complexity of Boolean quadratic forms
R. Mirwald, U. Frankfurt
C. Schnorr, U. Frankfurt
5:30 Break
9:00 Business Meeting
TUESDAY, OCTOBER 13
Session 5. Chair: Uzi Vishkin
8:30 Cascading divide-and-conquer: a technique for designing parallel
algorithms
M. Atallah, Purdue U.
R. Cole, N.Y.U.
M. Goodrich, Purdue U.
8:50 A new parallel algorithm for the maximal independent set problem
M. Goldberg, R.P.I.
T. Spencer, R.P.I.
9:10 The matching problem for bipartite graphs with polynomially
bounded permanents is in NC
D. Grigoriev, Soviet Academy of Sciences
M. Karpinski, U. Bonn
9:30 On the complexity of some computations with polynomials and
Toeplitz matrices
V. Pan, S.U.N.Y. Albany
J. Reif, Duke U.
9:50 Break
Session 6. Chair: Tom Leighton
10:20 How to emulate shared memory
A. Ranade, Yale U.
10:40 A lower bound of Omega(log log n) for randomized parallel merging
M. Gereb-Graus, Harvard U.
D. Krizanc, Harvard U.
11:00 The average complexity of deterministic and randomized parallel
comparison sorting algorithms
N. Alon, Tel Aviv U.
Y. Azar, Tel Aviv U.
11:20 Hierarchical memory with block transfer
A. Aggarwal, I.B.M. Watson Research Center
A. Chandra, I.B.M. Watson Research Center
M. Snir, I.B.M. Watson Research Center
11:40 Approximation algorithms for scheduling unrelated parallel
machines
J. Lenstra, C.W.I.
D. Shmoys, M.I.T.
E. Tardos, Eotvos U.
12:00 Lunch
Session 7. Chair: Robert Tarjan
2:00 Finding near optimal separators in planar graphs
S. Rao, M.I.T.
2:20 A parallel algorithm for finding a separator in planar graphs
H. Gazit, U. Southern California
G. Miller, U. Southern California
2:40 Determining edge connectivity in O(nm) steps
D. Matula, Southern Methodist U.
3:00 Improved algorithms for graph four-connectivity
A. Kanevsky, U. Illinois at Urbana
V. Ramachandran, U. Illinois at Urbana
3:20 Parallel graph algorithms that are efficient on average
D. Coppersmith, I.B.M. Watson Research Center
P. Raghavan, I.B.M. Watson Research Center
M. Tompa, I.B.M. Watson Research Center
3:40 Break
Session 8. Chair: Laszlo Babai
4:10 Canonical labeling of regular graphs in linear average time
L. Kucera, U. Chicago and Charles U.
4:30 Eigenvalues and graph bisection: an average-case analysis
R. Boppana, M.I.T.
4:50 On the second eigenvalue of random regular graphs
A. Broder, D.E.C.-S.R.C.
E. Shamir, D.E.C.-S.R.C. and U. Chicago
5:10 Recursive construction for 3-regular expanders
M. Ajtai, I.B.M. Almaden Research Center
5:30 Break
7:00 Banquet
WEDNESDAY, OCTOBER 14
Session 9. Chair: Rao Kosaraju
8:30 The organization of permutation architectures with bussed
interconnections
J. Kilian, M.I.T.
S. Kipnis, M.I.T.
C. Leiserson, M.I.T.
8:50 Channel routing of multiterminal nets
S. Gao, U. Saarlandes
M. Kaufmann, U. Saarlandes
9:10 Two lower bounds in asynchronous distributed computation
P. Duris, Slovak Academy Sciences
Z. Galil, Columbia U.
9:30 Locality as an obstacle to distributed computing
N. Linial, Hebrew U.
9:50 Break
Session 10. Chair: Paris Kanellakis
10:20 Achievable cases in an asynchronous environment
H. Attiya, Hebrew U.
A. Bar-Noy, Hebrew U.
D. Dolev, Hebrew U.
D. Koller, Hebrew U.
D. Peleg, Stanford U.
R. Reischuk, Technische Hochschule Darmstadt
10:40 Local management of a global resource in a communication network
Y. Afek, A.T.&T. Bell Labs
B. Awerbuch, M.I.T.
S. Plotkin, M.I.T.
M. Saks, Rutgers U. and Bell Communications Research
11:00 Applying static network protocols to dynamic networks
Y. Afek, A.T.&T. Bell Labs
B. Awerbuch, M.I.T.
E. Gafni, U.C.L.A.
11:20 Bounded time-stamps
A. Israeli, Harvard U.
M. Li, Harvard U.
11:40 Concurrent reading while writing II: the multi-writer case
G. Peterson, Georgia Tech.
J. Burns, Georgia Tech.
12:00 Lunch
Session 11. Chair: Joseph Halpern
2:00 Lower bounds to randomized algorithms for graph properties
A. Yao, Princeton U.
2:20 Exponential lower bounds for finding Brouwer fixed points
M. Hirsch, U.C. Berkeley
S. Vavasis, Stanford U.
2:40 Database theory and cylindric lattices
S. Cosmadakis, I.B.M. Watson Research Center
3:00 Secret linear congruential generators are not cryptographically
secure
J. Stern, U. Paris
3:20 A practical scheme for verifiable secret sharing
P. Feldman, M.I.T.
3:40 Break
Session 12. Chair: Shafi Goldwasser
4:10 Perfect zero-knowledge languages can be recognized in two rounds
W. Aiello, M.I.T.
J. Hastad, M.I.T.
4:30 Interactive proof systems: provers that never fail and random
selection
O. Goldreich, Technion
Y. Mansour, I.B.M. Haifa Scientific Center
4:50 On the cunning power of cheating verifiers: some observations
about zero knowledge proofs
Y. Oren, Technion
5:10 Random self-reducibility and zero knowledge interactive proofs
of possession of information
M. Tompa, I.B.M. Watson Research Center
H. Woll, U. Washington
5:30 End