kosaraju@crabcake.cs.jhu.EDU (Rao Kosaraju) (03/22/90)
TWENTY-SECOND ANNUAL
ACM SYMPOSIUM ON
THEORY OF COMPUTING
Sponsored by ACM SIGACT
Baltimore, Maryland
May 14-16, 1990
Local Arrangements Chair:
S. Rao Kosaraju
Program Committee Chair:
Harold Gabow
Program Committee:
Baruch Awerbuch S. Rao Kosaraju
Bernard Chazelle Dexter Kozen
Fan Chung Ian Munro
Ronald Fagin John Reif
Harold Gabow Janos Simon
Oded Goldreich Manfred Warmuth
STOC '90
REGISTRATION FORM
Category Fee Late Fee
(after 4/13)
ACM or SIGACT Member $230 $280
Neither ACM nor SIGACT Member $280 $330
Author or Program Committee Member $220 $270
Full-time Student $ 60 $110
Specify your membership number ___________________________________________
Registration fee includes: reception, 3 lunches, dinner cruise, coffee
breaks, and the proceedings.
Student registration fee includes: reception, lunches, coffee breaks
and proceedings, but not the dinner cruise.
Non-members can join SIGACT for free by checking the following line.
(A portion of your registration fee covers your first year's dues.)
Students can also get free ACM student membership.
_____ Please enroll me as a SIGACT member.
_____ I am a student; enroll me as an ACM student member also.
Additional dinner cruise tickets are $37 each.
Name: _______________________________________________________________
Affiliation: ________________________________________________________
Address: ____________________________________________________________
_____________________________________________________________________
Phone number: ______________________________E-mail: _________________
Dietary Restrictions: ___ Kosher ___ Vegetarian
Fill out the above registration form and mail with check to:
ACM STOC '90
c/o S. Rao Kosaraju
Department of Computer Science
The Johns Hopkins University
Baltimore, Maryland 21218
STOC '90
HOTEL RESERVATION FORM
May 14-16, 1990
Omni Inner Harbor Hotel
(30l)752-1100
Please circle the accommodation desired.
Single $ 98
Double $108
Triple $124
Quadruple $140
Name: ______________________________________________________________
Sharing with: ______________________________________________________
Affiliation: _______________________________________________________
Address: ___________________________________________________________
____________________________________________________________________
Day time phone number:______________________________________________
Arrival Date:__________________Arrival Time: _______________________
Departure Date: _______________Departure Time: _____________________
Arrivals after 6:00 pm must guarantee first nights accommodations with
check, money order, or major credit card.
Credit card company: _______________________________________________
Card number: _______________________________________________________
Expiration date: ____________________________________________________
Signature: _________________________________________________________
Send this form to:
Omni Inner Harbor Hotel
101 W.Fayatte Street
Baltimore, Maryland 21201
Reservations received after the contracted block of rooms is full or
after the cut-off date of April 13, 1990 are subject to space and rate
availability.
PROGRAM
All events except the dinner cruise are held at the Omni Hotel.
Reception, all technical sessions, and the business meeting will be
held in the Grand Ballroom on the first floor. During the day
Mencken Room on the first floor is available for small meetings.
Sunday Evening, May 13, 1990
8:00-11:00 Reception
Monday, May 14, 1990
Session 1 8:30-10:10
Chaired by Ian Munro, University of Waterloo
8:30 BLASTING Through the Information Theoretic Barrier with FUSION
TREES Michael L. Fredman, Rutgers, Bellcore and UCSD; Dan E.
Willard, SUNY at Albany.
8:50 On the Dynamic Finger Conjecture for Splay Trees Richard Cole,
Courant Institute.
9:10 Unique Binary Search Tree Representations and Equality-testing
of Sets and Sequences Rajamani Sundar, Courant
Institute; Robert E. Tarjan, Princeton University
and AT&T Bell Laboratories.
9:30 The Information Theory Bound is Tight for Selection in a Heap
Greg N. Frederickson, Purdue University.
9:50 Lower Bounds for the Union-find and the Split-find Problem on
Pointer Machines J. A. La Poutr'e, University of Utrecht.
Break 10:10-10:30
Session 2 10:30-12:10
Chaired by Manfred Warmuth, University of California, Santa Cruz
10:30 Optimal Randomized Algorithms for Local Sorting and Set-maxima
Wayne Goddard, Leonard Schulman, Massachusetts Institute
of Technology; Valerie King, University of Toronto.
10:50 On the Necessity of Occam Algorithms Raymond Board, Leonard
Pitt, Univesity of Illinois, Urbana.
11:10 Learning Boolean Functions in an Infinite Attribute Space
Avrim Blum, Massachusetts Institute of Technology.
11:30 Self-testing and Self-correcting Programs with Applications to
Numerical Problems Manuel Blum, Ronitt Rubinfeld, University of
California, Berkeley; Michael Luby, International Computer
Science Institute.
11:50 Coherent Functions and Program Checkers Andrew C.Yao,
Princeton University.
Lunch 12:10-1:30
Session 3 1:30-3:10
Chaired by Baruch Awerbuch, M.I.T.
1:30 The Use of a Synchronizer Yields Maximum Computation Rate in
Distributed Networks Shimon Even, Technion; Sergio Rajsbaum,
University of Texas at Dallas.
1:50 The Wakeup Problem Michael J. Fischer, Gadi Taubenfeld,
Yale University; Shlomo Moran, Technion; Steven Rudich, Carnegie
Mellon University.
2:10 How to Distribute a Dictionary in a Complete Network Martin
Dietzfelbinger, Friedhelm Meyer auf der Heide, University of Paderborn.
2:30 Computing with Unreliable Information Uriel Feige, David
Peleg, Weizmann Institute of Science; Prabhakar Raghavan, IBM
T.J. Watson Research Center; Eli Upfal, IBM
Almaden Research Center and Weizmann.
2:50 Efficient Robust Parallel Computations Zvi M. Kedem,Courant
Institute; Krishna Palem, IBM T.J. Watson Research Center; Paul
Spirakis, Patras University and Courant.
Break 3:10-3:30
Session 4 3:30-5:10
Chaired by John Reif, Duke University
3:30 On-line Algorithms for Path Selection in Nonblocking Networks
Sanjeev Arora, Tom Leighton, Bruce Maggs, Massachusetts
Institute of Technology.
3:50 Optimal Disk I/O with Parallel Block Transfer Jeffrey S.
Vitter, Brown University; Elizabeth A.M. Shriver, Bell
Communications Research.
4:10 Deterministic Sampling - A New Technique for Fast Pattern
Matching Uzi Vishkin, University of Maryland and Tel Aviv University.
4:30 Towards Overcoming the Transitive-closure Bottleneck: Efficient
Parallel Algorithms for Planar Digraphs Ming-Yang Kao, Duke
University; Philip N. Klein, Brown University.
4:50 Deterministic Sorting in Nearly Logarithmic Time on the
Hypercube and Related Computers Robert Cypher, IBM Almaden
Research Center; C. Greg Plaxton, Massachusetts
Institute of Technology.
8:30-11:00 SIGACT Business Meeting
Tuesday, May 15, 1990
Session 5 8:30-10:00
Chaired by Dexter Kozen, Cornell University
8:30 Pseudorandom Generators for Space-bounded Computation
Noam Nisan, Massachusetts Institute of Technology.
8:50 Small-bias Probability Spaces: Efficient Constructions and
Applications Joseph Naor, Stanford University; Moni Naor, IBM
Almaden Research Center.
9:10 The Analysis of Closed Hashing Under Limited Randomness
Jeanette P. Schmidt, Polytechnic University, Brooklyn; Alan
Siegel, Courant Institute.
9:30 The Computational Complexity of Universal Hashing Yishay
Mansour, Noam Nisan, Massachusetts Institute of
Technology; Prasoon Tiwari, IBM T.J. Watson Research Center.
9:50 Not All Keys Can Be Hashed in Constant Time Joseph Gil, Avi
Wigderson, Hebrew University; Friedhelm Meyer auf der
Heide, University of Paderborn.
Break 10:10-10:30
Session 6 10:30-12:10
Chaired by Janos Simon, University of Chicago
10:30 A Technique for Lower Bounding the Cover Time David
Zuckerman, University of California, Berkeley.
10:50 Approximate Inclusion-exclusion Nati Linial, IBM Almaden
Research Center, Stanford University, Hebrew University; Noam
Nisan, Massachusetts Institute of Technology.
11:10 Towards Optimal Simulations of Formulas by Bounded-width
Programs Richard Cleve, International Computer Science Institute.
11:30 Functions with Bounded Symmetric Communication Complexity and
Circuits with mod m Gates Mario Szegedy, Hebrew University.
11:50 Monotone Circuits for Matching Require Linear Depth Ran Raz,
Avi Wigderson, Hebrew University.
Lunch 12:10-1:30
Session 7 1:30-3:30
Chaired by Bernard Chazelle,Princeton University
1:30 A Separator Theorem for Graphs with an Excluded Minor and Its
Applications Noga Alon, IBM Almaden Research Center; Paul
Seymour, BellCore; Robin Thomas, Georgia Institute of Technology.
1:50 Separators in Two and Three Dimensions Gary L. Miller, Carnegie
Mellon University and University of Southern California;
William Thurston, Princeton University.
2:10 Leighton-Rao Might be Practical: A Faster Approximation
Algorithm for Uniform Concurrent Flow Philip Klein, Brown
University; Clifford Stein, Massachusetts Institute of
Technology; Eva Tardos, Cornell University.
2:30 Output-sensitive Construction of Voronoi Diagrams in Rd of
Order 1 to k Ketan Mulmuley, University of Chicago.
2:50 Solving Query-retrieval Problems by Compacting Voronoi Diagrams
Alok Aggarwal, IBM T.J. Watson Research Center and
Massachusetts Institute of Technology; Mark Hansen,
Tom Leighton, MIT.
3:10 Quantitative Steinitz's Theorems with Applications to
Multifingered Grasping David Kirkpatrick, University of British
Columbia; Bud Mishra, Chee-Keng Yap, Courant Institute.
Break 3:30-3:50
Session 8 3:50-5:10
Chaired by Harold Gabow, University of Colorado at Boulder
3:50 An Optimal Algorithm for On-line Bipartite Matching Richard M.
Karp, University of California, Berkeley and International
Computer Science Institute; Umesh V. Vazirani,
University of California, Berkeley; Vijay V. Vazirani, Cornell
University.
4:10 Online Algorithms for Locating Checkpoints M. Bern, D.
Greene, Xerox PARC; A. Raghunathan, Courant Institute; M.
Sudan, University of California, Berkeley.
4:30 Random Walks on Weighted Graphs, and Applications to On-Line
Algorithms Don Coppersmith, Prabhakar Raghavan, Marc Snir,
IBM T.J. Watson Research Center; Peter Doyle, AT&T Bell Laboratories.
4:50 On the Power of Randomization in Online Algorithms A.
Borodin, University of Toronto;
R. Karp, University of California, Berkeley and
International Computer Science Institute;
G. Tardos, Eotvos University; A. Wigderson, Hebrew University.
6:15-10:00 Dinner cruise on Bay Lady, Harbor Place
Wednesday, May 16, 1990
Session 9 8:30-10:10
Chaired by Oded Goldreich, Technion
8:30 One-way Functions are Necessary and Sufficient for Secure
Signatures John Rompel, Massachusetts Institute of Technology.
8:50 Pseudo-Random Generators under Uniform Assumptions Johan
Hastad, Royal Institute of Technology, Stockholm.
9:10 The Discrete Log is Very Discreet A.W. Schrift, A. Shamir,
Weizmann Institute of Science.
9:30 Witness Indistinguishability and Witness Hiding U. Feige, A.
Shamir, Weizmann Institute of Science.
9:50 Public-key Cryptosystems Provably Secure Against Chosen
Ciphertext Attacks, Moni Naor, IBM Almaden Research Center;
Moti Yung, IBM T.J. Watson Research Center.
Break 10:10-10:30
Session 10 10:30-12:10
Chaired by Ronald Fagin, IBM Almaden
10:30 On the Complexity of Local Search Christos H.
Papadimitriou, University of California, San Diego; Alejandro
A. Schaffer , Rice University; Mihalis Yannakis, AT&T Bell
Laboratories.
10:50 Quantifiers and Approximation Alessandro Panconesi, Desh
Ranjan, Cornell University.
11:10 On Polynomial Bounded Truth-Table Reducibility of NPSets to
Sparse Sets Mitsunori Ogiwara, Osamu Watanabe, Tokyo Institute
of Technology.
11:30 The Undecidability of the Semi-unification Problem A.J. Kfoury,
Boston University; J. Tiuryn, P. Urzyczyn, University of Warsaw.
11:50 Decidability of the Multiplicity Equivalence of Multitape
Finite Automata T.Harju, J. Karhumaki, University of Turku.
Lunch 12:10-1:30
Session 11 1:30-2:50
Chaired by Oded Goldreich, Technion
1:30 Perfect Zero-knowledge in Constant Rounds Mihir Bellare, Silvio
Micali, Rafail Ostrovsky, Massachusetts Institute of Technology.
1:50 The (True) Complexity of Statistical Zero Knowledge Mihir
Bellare, Silvio Micali, Rafail Ostrovsky, Massachusetts
Institute of Technology.
2:10 Cryptographically Secure Distributed Computation in a Constant
Number of Rounds Donald Beaver, Harvard University; Silvio
Micali, Phillip Rogaway, Massachusetts Institute of Technology.
2:30 Efficient Computation on an Oblivious RAM Rafail Ostrovsky,
Massachusetts Institute of Technology.
Break 2:50-3:10
Session 12 3:10-4:50
Chaired by Fan R. K. Chung, Bellcore
3:10 Computing in Quotient Groups William M. Kantor, Eugene M.
Luks, University of Oregon.
3:30 On the Decidability of Sparse Univariate Polynomial
Interpolation Allan Borodin, University of Toronto; Prasoon
Tiwari, IBM T.J.Watson Research Center.
3:50 Small Degree Primitive Roots over Finite Fields Victor
Shoup, AT&T Bell Laboratories.
4:10 On the Complexity of Computing a Grobner Basis for the Radical
of a Zero Dimensional Ideal Y. N. Lakshman, Rensselaer
Polytechnic Institute.
4:30 The Number Field Sieve A.K. Lenstra, Bellcore; H.W. Lenstra,
Jr., University of California, Berkeley; M.S. Manasse, DEC SRC;
J.M. Pollard, Tidmarsh, Reading.
GENERAL INFORMATION
CONFERENCE REGISTRATION:
There will be registration outside of the Grand Ballroom on Sunday,
May 13, from 8:00 to 10:00 pm. From Monday to Wednesday there will be a
registration and information desk set up outside the Grand Ballroom
from 8:30 am to 5:00 pm.
HOTEL INFORMATION:
The conference will be held at the Omni Inner Harbor Hotel,
Baltimore, which is conveniently located downtown in Charles Center,
two blocks from the Convention Center and Festival Hall, directly
across from the Baltimore Arena and connected to the Inner Harbor by
overhead walkways. A block of rooms is being held for the symposium
until the cut-off date, April 13, 1990. The symposium rate will be
honored up to three days prior to the symposium. Reservations received after
the block of rooms is full or after cut-off date are subject to space
and rate availability. Check-in time is 3:00pm and check-out time is
12:00 noon.
Child Care: Child care service is available; please contact the
concierge at (301) 385-6795.
TRANSPORTATION:
If you are flying you will arrive at Baltimore-Washington
International (BWI) Airport which is about 15 miles south of downtown
Baltimore. The BWI Shuttle (van) leaves the airport every
1/2 hour from outside the baggage claim area to the Omni at a one-way
cost of $5.75 or round-trip cost of $10.00. A taxi to Omni costs about
$13.00. (Flying to National Airport or Dulles Airport
is not recommended; however,there is limo/bus service connecting to BWI.)
To reach the hotel by car going south on I-95: through Fort McHenry
Tunnel, to 395 N(Exit 53) 1/2 mile to Pratt Street, turn right; two
blocks to Charles Street, turn left; four blocks to Fayette
Street, turn left; Omni is one block on the left. Going north on I-95;
take exit 53,395 N; 1/2 mile to Pratt Street, turn right; continue as
above. Going south on I-83 from 695: Go to end of expressway; turn
right at Fayette Street; Omni is 7 blocks on the left Going north on
Baltimore-Washington Parkway: becomes Russell Street; turn right onto
Pratt Street; go 5 blocks and turn left onto Charles Street; 4 blocks
and turn left onto Fayette Street; Omni is one block ahead on left.
The parking fee at the hotel, with hotel receipt, is $7.00 per day.
AIRLINE INFORMATION:
USAir has been designated the official carrier of STOC '90. This
special fare will offer a 40% discount off the standard round trip day
coach fare for travel within the Continental U.S. From within Canada,
USAir will allow 30% discount with no minimum stay requirement or a
35% discount with a 2 night minimum stay requirement. Additional
restrictions apply for discounts in international travel. These fares
are valid between May 11-19, 1990. To obtain this convention
discount, you or your travel agent must call US Air 1-800-334-8644; from
Canada 1-800-428-4322, Ext. 7702; and refer to Gold File No. 168555.
INFORMATION ABOUT BALTIMORE:
Baltimore has undergone a tremendous revitalization in recent
years. Baltimore's new showplace is the Inner Harbor area, where you
will find boutiques and cafes, as well as the National Aquarium,
Maryland Science Center, and the Pier 6 Concert Pavilion. Throughout
the summer the city sponsors Ethnic Festivals of every description,
culminating in a grand City Fair. Its historic sites include Fort
McHenry, the Edgar Allen Poe House, and the first frigate of the U.S.
Navy, the U.S.F. Constellation. The Baltimore Museum of Art, adjacent
to the Homewood campus of The Johns Hopkins University, and the
Walters Art Gallery, both house excellent permanent collections and
attract important traveling exhibitions. Other cultural facilities and
attractions include the Baltimore Symphony Orchestra, Center Stage,
the Lyric Opera House, Meyerhoff Symphony Hall, Morris A. Mechanic
Theatre, and Peabody Institute. Baltimore also is only an hour north of
Washington, D.C. and its treasure trove of monuments, museums,
libraries, parks, and theaters. In mid May the temperature range is
typically between 52 (11C) and 74 (23C) degrees. The relative
humidity is about 53 and there is 56% chance of sunshine.
FURTHER INFORMATION:
For further information, contact S. Rao Kosaraju, Computer Science
Department, The Johns Hopkins University, Baltimore, MD 21218. Phone
(30l) 338-8134; FAX (30l) 338-6134; email kosaraju@cs.jhu.edu.