arvind@utcsri.UUCP (Arvind Gupta) (02/05/87)
From: ava%btl.csnet@csnet-relay.arpa
Subject: STOC87 Program
19th Annual ACM Symposium on
THEORY OF COMPUTING
In cooperation with the IEEE-Computer Society
May 25-27, 1987
Grand Hyatt Hotel
New York, NY
ADVANCE REGISTRATION FORM
Mail check payable in US dollars to ACM - STOC 87 before
April 25, 1987 to:
STOC Registration
Prof. Dana May Latch
Dept. of CIS
Brooklyn College of CUNY
Brooklyn, NY 11210
Before 4/25 After 4/25
Member ACM, SIGACT, or IEEE-CS $185 ___ $235 ___
Non-member $215 ___ $265 ___
Student (no lunches) $50 ___ $80 ___
Authors/program committee $175 ___ $235 ___
One copy of the proceedings is included in the fee.
Extra lunches @ $35/meal Mon ___ Tue ___ Wed ___
Special lunch preference: Kosher ___ Vegetarian ___
Name _______________________________________________________
Affiliation ________________________________________________
Address ____________________________________________________
City _________________________ State ____________ Zip ______
Email address ______________________________________________
SIGACT MEMBERSHIP FORM
To become a member of SIGACT mail to:
Association for Computing Machinery
P.O. Box 9182
Church Street Station
New York, NY 10249
Student _________ School ___________________
ACM Member ______ ACM Number ___________________
Non-member ______
For ACM members the dues are $11, payable when national
membership is renewed. For students dues are $5.50, and for
non-members dues are $33. Please make checks payable to
ACM.
Name _______________________________________________________
Affiliation ________________________________________________
Address ____________________________________________________
City _________________________ State ____________ Zip ______
TO ORDER SYMPOSIUM PROCEEDINGS
Proceedings may be ordered directly from:
ACM Order Department
P.O. Box 64145
Baltimore, MD 21264
ACM Order Number is 508870.
For telephone inquiries, call (301) 528-4261.
For credit card orders, call toll-free (800) 342-6626
or (301) 528-4261 (in Maryland and outside of the USA).
HOTEL RESERVATION FORM
Mail before April 25, 1987 to:
ACM SIGACT Symposium on Theory of Computing
Grand Hyatt New York
Park Avenue at Grand Central
New York, NY 10017
Telephone: (212) 883-1234 Telex: 645601
Single $105/day _____ Double $105/day _____
Triple $125/day _____
Rates subject to New York State tax and New York City
occupancy tax. Check-in: 3 pm. Check-out: 12 noon.
Arrival Date _________________________________ Time ________
Departure Date ______________________________ Time ________
For arrivals after 6pm, the hotel requests that you
guarantee your room by providing a major credit card number
or a check for one night's deposit.
Credit Card ________ #__________________________ Exp. ______
Sharing room with: _________________________________________
Name _______________________________________________________
Address ____________________________________________________
City ______________________ State _____________ Zip _______
Telephone __________________________________________________
CONFERENCE INFORMATION
LOCATION. Technical sessions are at the Grand Hyatt Hotel,
on 42nd Street between Park and Lexington Avenues, adjacent
to Grand Central Terminal and across the street from the
East Side Airlines Terminal. Please make reservations
directly with the hotel. Rates and availability not
guaranteed after May 2, 1987.
TRANSPORTATION. All participants of STOC 1987 are urged to
use our official discount travel service, Direct Travel,
Inc., (800-858-8228 and 212-302-7870). Every 40 American
Airlines roundtrip air tickets booked through Direct Travel
provides a student participant free transportation. Direct
Travel will also fill your Amtrack needs. Participants
should mention STOC 1987 when contacting Direct Travel.
Major credit cards are preferred.
LOCAL TRANSPORTATION. From Kennedy Aiport, Carey Bus to
Grand Central is $8, Abbey's Airport Minibus to Grand Hyatt
is $11, and taxi is about $26. From La Guardia Airport,
Carey Bus to Grand Central is $6, Abbey's Airport Minibus to
Grand Hyatt is $8.00, and taxi is about $22. From Newark
Aiport, Olympia Trails to East Side Terminal is $5, Airport
Minibus to Grand Hyatt is $15.75, and taxi is about $26.
>From Penn Station, the subway to Grand Central is $1.
THINGS TO DO. New York City is lovely in the spring time.
Temperatures average in the mid-60's with a chance of
refreshing showers. The city is one of the world's cultural
centers: theater from Broadway musicals to off-Broadway
dramas, music from classical to jazz, museums from modern
art to American crafts, shopping from the Lower East Side to
glamorous Fifth Avenue, restaurants from northern Italian
cuisine to exotic Thai food, and sports from baseball to
tennis. There is an abundance of interesting
free/inexpensive activities: concerts in the parks, historic
walking tours, bus rides through the City, visits to the
Empire State Building or to the newly renovated South Street
Seaport, and even tram rides over the East River.
REGISTRATION AND RECEPTION. Initial registration will be
from 6-9 p.m., Sunday, May 24, outside of Ballrooms C&D. On
Monday through Wednesday the registration desk will be
located outside of Ballrooms C&D during the general
sessions. There will be a reception on Sunday night from 8
to 11 in Ballrooms C&D.
ASL SPRING MEETING. The 1987 Spring Meeting of the
Association for Symbolic Logic (ASL) will be held May 23 -
24, 1987, at the Graduate School and University Center of
CUNY, and the Courant Institute of Mathematical Sciences of
NYU. Program information can be obtained from Prof. M.
Davis, NYU - Courant Institute, 251 Mercer St., New York, NY
10012. A special session of invited addresses on topics of
particular interest to STOC participants is being planned
for Sunday afternoon.
TECHNICAL PROGRAM
MONDAY, MAY 25, 1987
SESSION 1. Chair: Alfred Aho Ballrooms C&D
9:00 Matrix Multiplication via Behrend's Theorem
D. Coppersmith and S. Winograd, IBM Watson
9:20 Solving Minimum-Cost Flow Problems by Successive
Approximation. A. Goldberg, MIT, and R. Tarjan,
Princeton and AT&T Bell Labs
9:40 A New Approach to All Pairs Shortest Paths in Planar
Graphs. Greg N. Frederickson, Purdue
10:00 An Algorithm for Linear Programming which Requires
O(((m+n)n sup 2 +(m+n) sup 1.5 n)L) Arithmetic
Operations. Pravin M. Vaidya, AT&T Bell Labs
10:20 Break
SESSION 2. Chair: Frances Yao Ballrooms C&D
11:00 A Linear Time Algorithm for Computing the Voronoi
Diagram of a Convex Polygon. A. Aggarwal, IBM Watson,
L. Guibas, Stanford and DEC SRC, J. Saxe, DEC SRC, and
P. Shor, AT&T Bell Laboratories
11:20 Testing for Cycles in Infinite Graphs with Periodic
Structure. K. Iwano and K. Steiglitz, Princeton
11:40 Approximation Algorithms for Shortest Path Motion
Planning. Ken Clarkson, AT&T Bell Laboratories
12:00 The Complexity of Cutting Convex Polytopes
B. Chazelle, Princeton, H. Edelsbrunner, Illinois, and
L. Guibas, Stanford and DEC SRC
12:20 Lunch Ballrooms A&B
SESSION 3. Chair: Michael Sipser Ballrooms C&D
2:00 Algebraic Methods in the Theory of Lower Bounds for
Boolean Circuit Complexity. R. Smolensky, UC Berkeley
2:20 Optimal Bounds for Decision Problems on the CRCW PRAM.
P. Beame and J. Hastad, MIT
2:40 Two Tapes Are Better than One for Offline Turing
Machines. W. Maass, Illinois, G. Schnitger, Penn.
State, and E. Szemeredi, Rutgers and Hungarian Academy
of Sciences
3:00 Finite Monoids and the Fine Structure of NC sup 1
D. Barrington, U. Mass., and D. Th'erien, McGill
3:20 Break
SESSION 4. Chair: Dexter Kozen Ballrooms C&D
4:00 The Strong Exponential Hierarchy Collapses
Lane A. Hemachandra, Cornell University
4:20 The Boolean Formula Value Problem is in ALOGTIME.
Samuel R. Buss, UC Berkeley
4:40 Deterministic Simulation in LOGSPACE
M. Ajtai, IBM ARC, J. Komlos, UC San Diego, and E.
Szemeredi, Rutgers
5:00 A Semi-Unboundedness Property that Characterizes
LOGCFL. H. Venkateswaran, Georgia Institute of Tech-
nology
BUSINESS MEETING, 9:00pm Ballrooms C&D
TUESDAY, MAY 26, 1987
SESSION 5. Chair: Michael Luby Ballrooms C&D
8:40 Some Consequences of the Existence of Pseudorandom
Generators. E. Allender, Rutgers
9:00 Efficiency Considerations in Using Semi-random
Sources. Umesh V. Vazirani, Harvard
9:20 Imperfect Random Sources and Discrete Controlled
Sources. D. Lichtenstein, Yale, N. Linial, Hebrew U.,
and M. Saks, Bell Communications Research and Rutgers
9:40 The Power of Randomness for Communication Complexity.
M. Furer, Zurich
10:00 Towards a Theory of Software Protection and Simulation
by Oblivious RAMs. Oded Goldreich, Technion
10:20 Break
SESSION 6. Chair: Manuel Blum Ballrooms C&D
11:00 On Hiding Information from an Oracle
M. Abadi, DEC SRC, J. Feigenbaum, AT&T Bell Labora-
tories, and J. Kilian, MIT
11:20 The Complexity of Perfect Zero-Knowledge
Lance Fortnow, MIT
11:40 Zero Knowledge Proofs of Identity
U. Feige, Weizmann, A. Fiat, UC Berkeley, and A.
Shamir, Weizmann
12:00 How to Play Any Mental Game
O. Goldreich, Technion, S. Micali, MIT, and A. Wigder-
son, Hebrew U.
12:20 Lunch Ballrooms A&B
SESSION 7. Chair: Joseph Halpern Ballrooms C&D
2:00 Optimal Distributed Algorithms for Minimum Weight
Spanning Tree, Counting, Leader Election and Related
Problems, B. Awerbuch, MIT
2:20 Analysis of Backoff Protocols for Multiple Access
Channels. J. Hastad, T. Leighton, and M. Rogoff, MIT
2:40 Dynamic Parallel Complexity of Computational Circuits.
G. Miller and S. Teng, USC
3:00 Constructing Disjoint Paths on Expander Graphs. D.
Peleg, Stanford, and E. Upfal, IBM ARC
3:20 Reconfiguring a Hypercube in the Presence of Faults.
J. Hastad, T. Leighton, and M. Newman, MIT
3:40 Break
SESSION 8. Chair: Joseph Halpern Ballrooms C&D
4:10 On the Learnability of Boolean Formulae
M. Kearns, Harvard, M. Li, Harvard, L. Pitt, Illinois,
and L. Valiant, Harvard
4:30 On Learning Boolean Functions
B. K. Natarajan, CMU
4:50 An Hierarchical Memory Model
A. Aggarwal, B. Alpern and A. Chandra, IBM Watson
5:10 Parallel Symmetry-Breaking in Sparse Graphs.
A. Goldberg, MIT, S. Plotkin, MIT, and
G. Shannon, Purdue
WEDNESDAY, MAY 27, 1987
SESSION 9. Chair: Michael Luby Ballrooms C&D
9:00 A Random NC Algorithm for Depth First Search
A. Aggarwal, IBM Watson, and R. Anderson, Washington
9:20 A New Graph Triconnectivity Algorithm and Its Paral-
lelization. G. Miller, USC, and V. Ramachandran,
Illinois
9:40 Matching is as Easy as Matrix Inversion
K. Mulmuley, UC Berkeley, U. V. Vazirani, Harvard, and
V. V. Vazirani, AT&T Bell Labs
10:00 Fast Parallel Algorithms for Chordal Graphs
J. Naor, Hebrew U., M. Naor, UC Berkeley, and A.
Schaffer, Stanford U.
10:20 Break
SESSION 10. Chair: Andrea LaPaugh Ballrooms C&D
11:00 Two Algorithms for Maintaining Order in a List
P. Dietz, Schlumberger-Doll, D. Sleator, CMU
11:20 An Optimal Online Algorithm for Metrical Task Systems.
A. Borodin, Toronto, N. Linial, Hebrew U., and M.
Saks, Rutgers and Bell Communications Research
11:40 Searching a Two Key Table Under a Single Key
J. Ian Munro, Waterloo
12:00 The Pagenumber of Genus g Graphs is O(g)
L. Heath, MIT, and S. Istrail, Wesleyan
12:20 Lunch Ballrooms A&B
SESSION 11. Chair: Manuel Blum Ballrooms C&D
2:00 Simple Algebras are Difficult
L. Ronyai, Hungarian Academy of Sciences
2:20 Permutation Groups in NC
L. Babai, Eotvos and Chicago, E. Luks, Oregon, and A.
Seress, Hungarian Academy of Sciences
2:40 Zero-One Laws for Sparse Random Graphs
S. Shelah, Jerusalem, and J. Spencer, Stony Brook
3:00 The Decision Problem for the Probabilities of Higher-
Order Properties. P. Kolaitis and M. Vardi, IBM ARC
3:20 Break
SESSION 12. Chair: Michael Sipser Ballrooms C&D
3:40 Size-Time Complexity of Boolean Networks for Prefix
Computations. G. Bilardi, Cornell, and F. P.
Preparata, Illinois
4:00 Single-Factor Hensel Lifting and its Application to
the Straight-Line Complexity of Certain Polynomials.
Erich Kaltofen, RPI
4:20 Realistic Analysis of Some Randomized Algorithms.
Eric Bach, Wisconsin
4:40 Recognizing Primes in Random Polynomial Time. L.
Adleman and M. Huang, USC
5:00 Adjourn
PROGRAM COMMITTEE
A. Aho, M. Blum, J. Halpern, R. Kannan, D. Kozen, A.
LaPaugh, M. Luby, C. Papadimitriou, M. Sipser, F. Yao.
UNIVERSITY SUPPORTERS
Brooklyn College - CUNY
Brooklyn, NY 11210
Graduate School and University Center
City University of New York
New York, NY 10036
INSTITUTIONAL SUPPORTERS
Addison-Wesley Publishing Co.
Reading, MA 01867
AT & T Bell Laboratories
Murray Hill, NJ 07974
Bell Communications Research
Morristown, NJ 07960
Computer Science Press Inc.
Rockville, MD 20850
Digital Equipment Corporation
Systems Research Center
Palo Alto, CA 94301
General Electric Research and Development Center
Schenectady, NY 12301
IBM, Almaden Research Center
San Jose, CA 95120-6099
IBM, Thomas J. Watson Research Center
Yorktown Heights, NY 10598
Instituto di Analisi dei Sistemi ed Informatica
I-00185 ROMA, Italy
Morgan Kaufman Publishers, Inc.
Los Altos, CA 94022
Tektronix Computer Research Laboratory
Beaverton, OR 97077
Xerox Palo Alto Research Center
Palo Alto, CA 94304
FOR FURTHER INFORMATION
Conference Chair:
Prof. Dana May Latch
Dept. of CIS
Brooklyn College - CUNY
Brooklyn, NY 11210
dml@cunyvms1.bitnet
(718) 780-5657
Program Chair:
Dr. Alfred V. Aho
Computing Science Research Center
Room 2C-326
AT&T Bell Laboratories
Murray Hill, NJ 07974
SIGACT Chair:
Prof. Zvi Galil
Dept. of Computer Science
Columbia University
New York, NY 10027