Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site utcsri.UUCP Path: utzoo!utcsri!arvind From: arvind@utcsri.UUCP (Arvind Gupta) Newsgroups: ut.theory Subject: STOC program Message-ID: <4070@utcsri.UUCP> Date: Thu, 5-Feb-87 10:32:27 EST Article-I.D.: utcsri.4070 Posted: Thu Feb 5 10:32:27 1987 Date-Received: Thu, 5-Feb-87 18:42:40 EST Distribution: ut Organization: CSRI, University of Toronto Lines: 481 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