arvind@theory.toronto.edu (Arvind Gupta) (05/08/89)
> From yonge.csri.toronto.edu!VM1.NoDak.EDU!THEORYNT Sat May 6 19:45:00 1989 > Received: from yonge.csri.toronto.edu by neat.ai.toronto.edu with SMTP id 39776; Sat, 6 May 89 19:44:56 EDT > Received: from VM1.NoDak.EDU (-:VM1.NODAK.EDU:-) by yonge.csri.toronto.edu via TCP with SMTP id AA05342; Sat, 6 May 89 19:42:48 EDT > Message-Id: <8905062342.AA05342@yonge.csri.toronto.edu> > Received: from NDSUVM1.BITNET by VM1.NoDak.EDU (IBM VM SMTP R1.2.1MX) with BSMTP id 7620; Sat, 06 May 89 14:39:57 CDT > Received: by NDSUVM1 (Mailer R2.03B) id 6923; Sat, 06 May 89 03:37:18 CDT > Date: Sat, 6 May 89 04:25:01 EDT > Reply-To: Theory-A - TheoryNet World-Wide Events <THEORY-A@VM1.NoDak.EDU>, > ftl@MATH.MIT.EDU > Sender: TheoryNet List <THEORYNT@VM1.NoDak.EDU> > Comments: Warning -- original Sender: tag was THEORYNT@YKTVMX > Comments: Warning -- original Sender: tag was THEORY-A@NDSUVM1 > From: ftl%MATH.MIT.EDU@VM1.NoDak.EDU > To: Arvind Gupta <arvind@CSRI.TORONTO.EDU> The 1st Annual ACM Symposium on Parallel Algorithms and Architectures will be held in Santa Fe, New Mexico on June 18-21, 1989. Program and registration information follows. For more information, contact Tom Leighton or Ernie Brickell. If you would like to be put on the SPAA mailing list, contact Donna Baglio at ACM (baglio@acmvm.bitnet). Please note that the registration deadlines are fast approaching. In particular, THE HOTELS NEED YOUR RESERVATION BY MAY 18! So it might be best to call them to be gaurantee a room. Hardcopies of this announcement are currently being mailed to the mailing lists for SPAA, SIGACT, SIGARCH and EATCS. SPAA Registration Form Registration Fee (register by 5/31/89 to get the early rate) ACM, SIGARCH and/or SIGACT members $150 (early) or $175 (late) students $40 (early) or $50 (late) all others $175 (early) or $200 (late) Registration fee includes: Sunday reception, Monday lunch, Tuesday banquet, daily continental breakfast and coffee breaks. It also includes a copy of the proceedings. Student registration fee includes all of the above except the banquet. Number ____ of additional banquet tickets @ $32 each __ Indicate the number in your party intending to go on the bus to Bandelier on Sunday afternoon. Name__________________________________________ Affiliation___________________________________ Address_______________________________________ Phone_________________________________________ E-Mail________________________________________ Dietary Restrictions: __ Kosher __ Vegetarian Fill out the above registration form and mail with check to: SPAA 89 c/o Ernest Brickell, 1423 Sandia National Laboratories Albuquerque, NM 87185 SPAA 89 Hotel Reservation Form June 19-21, 1989 We will be using two hotels for the conference. All conference events will take place in the Hilton. However, we only have 100 rooms reserved in the Hilton. The El Dorado is located just across the street from the Hilton and we have another 100 rooms reserved there. Please send this reservation form to the hotel of your choice. If it is full, the hotel will send it to the other hotel. If the price difference makes this unacceptable for you, please indicate that on the form. The quoted room rates will apply for the period June 17 -June 21. Hilton of Santa Fe El Dorado Hotel 100 Sandoval Street 309 W. San Francisco St. Santa Fe, NM 87501 Santa Fe, NM 87501 (505)-988-2611 (505)-988-4455 (800)-336-3676 Single $65 Single $85 Double $75 Double $85 Triple $85 Triple $105 Quad $95 Quad $125 Name____________________________ Sharing with____________________ Affiliation_____________________ Address_________________________ Day time phone number___________ Arrival date______________ Arrival time____________ Departure date____________ Departure time__________ Arrivals after 4:00 pm must guarantee first nights accommodations with check, money order, or major credit card. Guarantees are recommended in any case since travel delays often cause late arrivals. Credit card company______________ Card number______________________ Expiration date__________________ Signature________________________ Reservations received after the contracted block of rooms is full or after the cut-off date of May 18 are subject to space and rate availability. Early reservations are essential because a complete sellout of hotel space in Santa Fe is not uncommon. Location : All conference events will take place in the Mesa Ballroom of the Hilton of Santa Fe. The Hilton is located just off of the historic Plaza of Santa Fe. Rooms have been reserved at the Hilton (505)988-2811 and the El Dorado (505) 988-4455 which is across the street from the Hilton. Reservations should be made before May 18, 1989 using the enclosed reservation form or by calling the hotel. Registration: A registration desk will be set up on the Promenade just outside of the Ballroom. It will be open from 7:00 pm to 9:00 pm Sunday, June 18 and during the sessions. Transportation: Albuquerque International Airport is sixty miles southwest of Santa Fe. The most convenient means of transportation from the airport to Santa Fe is via the Shuttlejack Bus. Shuttlejack provides ten trips daily from the airport to the Hilton of Santa Fe. The first departure is at 6:50 a.m., the last at 10:15 p.m. The cost is fifteen or twenty dollars and travel time is about seventy-five minutes. Reservations are recommended (505-982-4311, or toll-free outside of New Mexico, 1-800-452-2665). Mesa Airlines has frequently daily commuter service from the Albuquerque Airport to the Santa Fe Airport (505-842-4414). Fares vary, but the lowest is about $12. However, the Santa Fe Airport is about twelve miles from the Plaza and the taxi costs about $13 plus tax. The only taxi company in Santa Fe is Capitol City Cab (505-989-8888). Avis, Budget, Hertz, and National Rental Cars have offices at the Albuquerque Airport. If you drive from the airport, exit the Airport on Yale Boulevard, turn left on Gibson, and then enter I-25 North. The first exit for Santa Fe is Cerrillos Road North which leads to the Plaza. Near the Plaza, take Sandoval Street which forks off to the left. The Hilton and the El Dorado are located on Sandoval Street. Information about Santa Fe: Santa Fe is the oldest capital city in the United States, dating from 1610 AD, and today it is a cultural center of the Southwest. It is a pleasure to walk its narrow streets surrounded by historic adobe buildings containing galleries, shops, restaurants and five museums. Santa Fe is nestled in the foothills of the forests, parks, campgrounds and monuments within a sixty mile radius. Numerous Indian pueblos exist in the vicinity of Santa Fe. Native Americans from nearby Indian pueblos daily sell authentic hand-made native crafts under the portal of the Palace. Climate: Although located in the sunny Southwest, Santa Fe's climate is moderated by its elevation of 7000 feet. Daytime highs should be a comfortable 70 -80 degrees Fahrenheit, with evening temperatures dropping into the 50's. A light jacket or sweater is recommended for these cool evenings. Sunday outing: On Sunday afternoon, we have organized an excursion to Bandelier National Monument, which is located about 60 miles west of Santa Fe. Bandelier is an extensive, beautifully-situated Anasazi Indian ruin, with cliff dwellings, ceremonial kivas, and other structures which date from the twelfth to the fifteenth centuries. It also contains 37,000 acres of wilderness, waterfalls and wildlife, accessed by 60 miles of trails. If there is sufficient interest, we will charter a bus which will leave Santa Fe at 1:00 pm, June 18 and return at 6:00 pm. The cost will be about $10 to $20 depending on the number of participants. For the more adventurous, June is a good time for white water rafting in New Mexico. Further Information: For further information contact Ernie Brickell, Div. 1423, Sandia National Laboratories, Albuquerque, NM 87185, (505)-846-7564. Student support: Some travel money is available for students from Sandia National Laboratories. Priority will be given to speakers and authors. If interested send a request to Ernie Brickell by May 12. Reception and Banquet: There will be a reception Sunday evening at the Hilton hotel. There will be a conference banquet Tuesday, also at the Hilton. Business Meeting: There will be a business meeting on Monday evening at the Hilton. All registrants are encouraged to attend. Among other things, we will discuss the scope, size and location of future SPAAs. SESSIONS -------------------------------------------------------------------------- Monday, June 19, 1989 SESSION 1: Sartaj Sahni 8:30 A Framework for Adaptive Routing John Y. Ngai, Charles L. Seitz in Multicomputer Networks 8:55 On Communication Latency in Alok Aggarwal, PRAM Computations Ashok K. Chandra, Marc Snir 9:20 The Communication Complexity Jeff Chu, Georg Schnitger of Several Problems in Matrix Computation 9:45 Cost-bandwidth Tradeoffs for Marc Snir, Clyde P. Kruskal Communication Networks 10:10 Break 10:30 Processor Networks and Clyde P. Kruskal, Richard Beigel Interconnection Networks without Long Wires 10:55 Embedding of d-Dimensional Grids M.Y. Chan Into Optimal Hypercubes 11:20 A Lower Bound on the Size of Robert Cypher Shellsort Sorting Networks 11:45 Load Balancing, Selection and C. Greg Plaxton Sorting on the Hypercube 12:10 Lunch ------------------------------------------------------------------------- Monday, June 19, 1989 SESSION 2: Alok Aggarwal 2:00 Towards Understanding Exclusive Read Faith E. Fich, Avi Wigderson 2:25 Parallel RAMs with Bounded Memory Stephen J. Bellantoni Wordsize 2:50 The Power of Parallel Pointer Walter L. Ruzzo, Tak Wah Lam Manipulation 3:15 Deterministic P-RAM Simulation with Scot W. Hornick, Constant Redundancy Franco P. Preparata 3:40 Break 4:00 On the Parallel Complexity of Integer Xiaotie Deng Programming 4:25 Fast Parallel Algorithms for the Dennis Shasha, Kaizhong Zhang Unit Cost Editing Distance Between Trees 4:50 Intersecting Line Segments in Michael T. Goodrich Parallel with an Output-Sensitive Number of Processors ------------------------------------------------------------------------ Tuesday, June 20, 1989 SESSION 3: Faith Fich 8:30 Square Meshes Are Not Always Optimal Amotz Bar-Noy, David Peleg 8:55 Parallel Graph Contraction Cynthia A. Phillips 9:20 A More Practical PRAM Model Phillip B. Gibbons 9:45 The APRAM: Incorporating Asynchrony Richard Cole, Ofer Zajicek into the PRAM Model 10:10 Break 10:30 Fault Tolerance in Hypercube- Fred Annexstein derivative Networks 10:55 Locating Faults in a Constant Richard Beigel, S. Rao Kosaraju, Number of Parallel Testing Rounds Gregory F. Sullivan 11:20 The Virtual Time Machine Richard M. Fujimoto 11:45 A Lazy Cache Algorithm Yehuda Afek, Geoffrey Brown, Michael Merritt 12:10 Lunch ---------------------------------------------------------------------------- Tuesday, June 20, 1989 SESSION 4: Thomas Lengauer 2:00 Dynamic Tree Embeddings in Tom Leighton, Mark Newman, Butterflies and Hypercubes Eric Schwabe, Abhiram G. Ranade 2:25 Optimal On-line Load Balancing Gregory E. Shannon 2:50 Matching Partition a Linked List Yijie Han and Its Optimization 3:15 Lower Bounds and Efficient Paul Spirakis, Hermann Jung, Algorithms for Multiprocessor Lefteris Kirousis Scheduling of Dags with Communication Delays 3:40 Break 4:00 Optimal VLSI Architectures for Gianfranco Bilardi, Scot W. Multidimensional DFT Hornick, Majid Sarrafzadeh 4:25 Advances in Homotopic Layout Shaodi Gao, Michael Kaufmann, Compaction F. Miller Maley 4:50 Systolic Implementations of a Clark D. Thomborson, Move-to-Front Text Compressor Belle W.-Y. Wei -------------------------------------------------------------------------- Wednesday, June 21, 1989 SESSION 5: Gary Miller 8:30 Four Vector-Matrix Primitives Cynthia A. Phillips, Ajit Agrawal, Guy E. Blelloch, Robert L. Krawitz 8:55 Run-Time Parallelization and Ravi Mirchandaney, Scheduling of Loops Joel H. Saltz, Doug Baxter 9:20 Conflict-free Access of Arrays D-L. Lee, Y.H. Wang in a Parallel Processor 9:45 On the Number of Rounds Necessary B. Monien, S. Even to Disseminate Information 10:10 Break 10:30 A 2n-2 Step Algorithm for Routing Tom Leighton, Fillia Makedon, in an n x n Array With Constant Ioannis G. Tollis Size Queues 10:55 Multi-Packet-Routing on Mesh Manfred Kunde, Thomas Tensi Connected Arrays 11:20 Robust Algorithms for Packet Prabhakar Raghavan Routing in a Mesh 11:45 Technologies for Low Latency Thomas F. Knight, Jr. Interconnection Switches 12:10 Lunch -------------------------------------------------------------------------- Wednesday, June 21, 1989 SESSION 6: Quentin Stout 2:00 An Optimal Parallel Dictionary Friedhelm Meyer auf der Heide, Martin Dietzfelbinger 2:25 Efficient Parallel Algorithms for Joan M. Lucas, Path Problems in Directed Graphs Marian Gunsher Sackrowitz 2:50 An Efficient Parallel Algorithm for Marek Chrobak, Joseph Naor Computing a Large Independent Set in a Planar Graph 3:15 Optimal Parallel Suffix-Prefix Gad M. Landau, Zvi M. Kedem, Matching Algorithm and Applications Krishna V. Palem 3:40 Break 4:00 Optimal Parallel Algorithms for Jeffrey S. Vitter, Transitive Closure and Point Roberto Tamassia Location in Planar Structures 4:25 On Parallel Evaluation of Game Trees Yanjun Zhang, Richard M. Karp 4:50 Constructing Trees in Parallel G.L. Miller, M.J. Atallah, S.R. Kosaraju, L.L. Larmore, S-H. Teng ---------------------------------------------------------------------------