arvind@utcsri.UUCP (Arvind Gupta) (02/05/87)
From: Al Aho <ava%btl@relay.cs.net>
Subject: Announcement for STOC 87
19th Annual
ACM Symposium
on
Theory of Computing
In cooperation with
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 ____________________________________________
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.
Transporation. 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.
delim $$ gsize 9 gfont 3
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 $ roman NC sup 1$
D. Barrington, U. Mass., and D. Therien, 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 Technology
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 Laboratories, 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. Wigderson, 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 Parallelization.
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
UNIVERSITY SUPPORTERS
Brooklyn College - CUNY
Brooklyn, NY 11210
Graduate School and University Center
City University of New York
New York, NY 10036
For Further Information. Contact the Conference Chair:
Prof. Dana May Latch, Dept. of CIS
Brooklyn College - CUNY
Brooklyn, NY 11210
(718) 780-5657, dml@cunyvms1.bitnet
Program Committee. A. Aho (chair), M. Blum, J. Halpern, R. Kannan, D.
Kozen, A. LaPaugh, M. Luby, C. Papadimitriou, M. Sipser, F. Yao.
SIGACT Chair. Zvi Galil, Dept. of Computer Science, Columbia University,
New York, NY 10027.