🚀 go-pugleaf

> 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
---------------------------------------------------------------------------