Note: This version of the program was produced by Latex2HTML. While this program does a very good job, there were a few problems that had to be corrected by hand. We cannot guarantee that this version of the program is completely accurate, and would prefer that you use the LaTeX or PostScript versions that are available on the STOC web page. You should certainly use the other versions for printing registration forms (for either the conference or the hotel).


STOC'98

The 30th Annual
ACM Symposium on
Theory of Computing

Dallas, Texas
May 24-May 26, 1998

Sponsored by ACM SIGACT

with support from Microsoft




Registration for STOC'98

To qualify for the early registration fee, your registration application must be postmarked by Thursday, April 30, 1998. The non-student registration fee includes the Saturday night reception, the Sunday night business meeting, the Monday night banquet, coffee breaks, lunches, and a copy of the proceedings. The student fee includes all of the above except the banquet.

Mail the form below, along with credit card information or a check or money order in U.S. currency drawn through a U.S. bank, made payable to ACM/STOC'98.

STOC '98
Computer Science Program
University of Texas at Dallas
P.O. Box 830688, EC 31
Richardson, TX 75083-0688

Name

Address

Email

Phone FAX

Special Needs (Please specify)

Affiliation (as you wish it to appear on your name tag):

Please circle one amount below and fill in your membership number if appropriate: #.

Registrants in the ``Other'' category will automatically become SIGACT members for a period of one year.


  Fee (US$) after April 30
ACM or SIGACT Member 315 390
Student 125 190
Other 390 465


Check your dietary preference:
Kosher $\Box$ Vegetarian $\Box$ No Restriction $\Box$

Number of additional proceedings $54 each:

Number of additional Banquet tickets $55 each:

Total included: $

Credit Card Information (if applicable):
VISA / MasterCard / American Express (circle one)
Card #
Exp. Date:
Signature

Hotel Reservations
Deadline: April 30, 1998
The conference will be held at the Fairmont Hotel, Dallas, Texas. The rates for STOC'98 are posted below and apply from May 21 to May 29.

Reservation requests received by the hotel after the April 30 deadline are at your own risk: availability and rates are then no longer guaranteed. Refer to STOC'98 when making your reservations to obtain the rates listed.

To make reservations by phone, call (800) 527-4727 or (214) 720-2020.

To make reservations by fax or by mail, fill out the form below and fax it to fax (214) 720-5269, or mail it to the following address.

The Fairmont Hotel
ATTN: STOC'98 registration
1717 North Akard Street
Dallas, TX 75201, USA

Credit card information or a deposit (in the form of a check or money order for one night's stay made payable to the The Fairmont Hotel) must be included. Deposits will be refunded if the hotel is notified prior to 72 hours before arrival.

Rate: $95 plus tax for a single room, $105 plus tax for a double room. A rollaway bed is available for an extra charge of $25 per night.


Check room type: Single $\Box$ Double $\Box$
Smoking $\Box$ Non-smoking $\Box$

Arrival date   Departure date
check-in time: 3:00 pm check-out time: 1:00 pm

Name

Address

Phone

Sharing with

If paying by credit card please complete:
American Express $\Box$Master Card $\Box$Visa $\Box$
Carte Blanche $\Box$Diner's Club $\Box$Discover $\Box$


Credit Card #
Expiration date
I authorize The Fairmont Hotel, Dallas, TX, to charge the above account for the amount equal to one night's stay in case of a no-show.



Signature

SATURDAY, MAY 23, 1998


Reception: 7:30 pm-10:30 pm



SUNDAY, MAY 24, 1998


Continental Breakfast: 7:30am-8:25am


Session 1A: 8:25am-9:35am
Chair: Russell Impagliazzo

8:25
On the Limits of Non-Approximability of Lattice Problems: Oded Goldreich, Weizmann Institute; Shafi Goldwasser, MIT.

8:50
The Shortest Vector Problem in L2 is NP-Hard for Randomized Reductions: Miklós Ajtai, IBM.

9:15
Quantum Circuits with Mixed States: Dorit Aharonov, Hebrew Univ.; Alexei Kitaev, Landau Institute for Theoretical Physics, Moscow; Noam Nisan, Hebrew Univ.


Session 1B: 8:25am-9:35am
Chair: Milena Mihail

8:25
Exact Sampling and Approximate Counting Techniques: Mark L. Huber, Cornell Univ.

8:50
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem: Assaf Natanzon, Tel Aviv Univ.; Ron Shamir, Tel Aviv Univ. and Univ. of Washington; Roded Sharan, Tel Aviv Univ.

9:15
Improved Approximation Algorithms for Multiway Cut: Gruia Calinescu, Howard Karloff, Georgia Tech; Yuval Rabani, Technion.


Break: 9:35am-10:10am


Session 2A: 10:10am-10:55am
Chair: Michael Kearns

10:10
A Framework for Fast Quantum Mechanical Algorithms: Lov K. Grover, Bell Labs.

10:35
Quantum vs. Classical Communication and Computation: Harry Buhrman, CWI, Amsterdam; Richard Cleve, Univ. of Calgary; Avi Wigderson, Hebrew Univ.


Session 2B: 10:10am-10:55am
Chair: Serge Plotkin

10:10
Finding Maximum Flows in Simple Undirected Graphs is Easier than Bipartite Matching: David R. Karger, Matthew S. Levine, MIT.

10:35
Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-edge and Biconnectivity: Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup, Univ. of Copenhagen.




Invited talk: 11:00 am-12:00 noon
Chair: Fan Chung Graham
11:00
Developments in Quantum Computing: Peter Shor, AT&T Labs.




Lunch break: 12:00 noon- 1:40pm


Session 3A: 1:40pm-3:15pm
Chair: S. Muthu Muthukrishnan

1:40
Approximating the Bandwidth via Volume Respecting Embeddings: Uriel Feige, Weizmann Institute.

2:05
Semi-definite Relaxations for Minimum Bandwidth and Other Vertex-Ordering Problems: Avrim Blum, Goran Konjevod, R. Ravi, CMU; Santosh Vempala, CMU and MIT.

2:30
Approximation Schemes for the Euclidean k-medians and Related Problem: Sanjeev Arora, Princeton; Prabhakar Raghavan, IBM; Satish Rao, NEC.

2:55
Rounding via Tree: Deterministic Approximation Algorithms for Group Steiner Trees and k-median: M. Charikar, C. Chekuri, A. Goel, S. Guha, Stanford.


Session 3B: 1:40pm-3:15pm
Chair: Carsten Lund

1:40
The Cost of the Missing Bit: Communication Complexity with Help: László Babai, Thomas Hayes, Peter Kimmel, Univ. of Chicago.

2:05
Perfect One-Way Probablilistic Hash Functions: Ran Canetti, IBM; Daniele Micciancio, MIT; O. Reingold, Weizmann Institute.

2:30
Non-Interactive and Non-Malleable Commitment: Giovanni Di Crescenzo, U. C. S. D.; Yuval Ishai, Technion; Rafail Ostrovsky, Bellcore.

2:55
Protecting Data Privacy in Private Information Retrieval Schemes: Yael Gertner, U. of Pennsylvania; Yuval Ishai, Eyal Kushilevitz, Technion; Tal Malkin, MIT.


Break: 3:15pm-3:50pm


Session 4A: 3:50pm-5:50pm
Chair: Tandy Warnow

3:50
On Approximating Arbitrary Metrics by Tree Metrics: Yair Bartal, Bell Labs.

4:15
Trees and Euclidean Metrics: Nathan Linial, Avner Magen, Hebrew Univ.; Michael Saks, Rutgers.

4:40
Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness: Marcus Peinado, Thomas Lengauer, GMD, Germany.

5:05
Efficient Algorithms for Constructing Fault Tolerant Geometric Spanners: Christos Levcopoulos, Lund Univ., Sweden; Giri Narasimhan, Univ. of Memphis; Michiel Smid, U. of Magdeburg, Germany.

5:30
Almost Optimal Dispersers: Amnon Ta-Shma, ICSI.


Session 4B: 3:50pm-5:50pm
Chair: Ramarathnam Venkatesan

3:50
NP Might Not be as Easy as Detecting Unique Solutions: Richard Beigel, Lehigh Univ.; Harry Buhrman, CWI, Amsterdam; Lance Fortnow, U. of Chicago.

4:15
The Random Oracle Mothodology, Revisited: Ran Canetti, IBM; Oded Goldreich, Weizmann; Shai Halevi, IBM.

4:40
Randomized Complexity Lower Bounds: D. Grigoriev, Penn State.

5:05
Weak Alternating Automata and Tree Automata Emptiness: Orna Kupferman, Berkeley; Moshe Vardi, Rice Univ.

5:30
Over Words, Two Variables are as Powerful as One Quantifier Alternation: $\mbox{FO}^2 = \Sigma_2 \cap \Pi_2$: Denis Thérien, McGill Univ.; Thomas Wilke, Institut für Informatik und Praktische Mathematik, Germany.


Business Meeting: 9pm-11pm


MONDAY, MAY 25


Continental Breakfast: 7:30am-8:25am


Session 5A: 8:25am-9:35am
Chair: Ran Raz

8:25
Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound: M. Amin Shokrollahi, ICSI; Hal Wasserman, Berkeley.

8:50
Analysis of Low Density Codes and Improved Designs Using Irregular Graphs: Michael Luby, ICSI; Michael Mitzenmacher, DEC; Amin Shokrollahi, ICSI; Dan Spielman, MIT.

9:15
Spot-Checkers: Funda Ergün, Sampath Kannan, U. of Pennsylvania; S Ravi Kumar, Ronitt Rubinfeld, Cornell; Mahesh Vishwanathan, U. of Pennsylvania.


Session 5B: 8:25am-9:35am
Chair: Ramaramohan Paturi

8:25
The Power of a Pebble: Exploring and Mapping Directed Graphs: Michael A. Bender, Harvard; Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadham, MIT.

8:50
Linear-Time Pointer-Machine Algorithms for LCAs, MST Verification, and Dominators: Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook, AT&T Labs.

9:15
A Sublinear Bipartitness Tester for Bounded Degree Graphs: Oded Goldreich, Weizmann Institute; Dana Ron, MIT.


Session 6A: 10:10am-10:55am
Chair: Ramarathnam Venkatesan

10:10
Recycling Queries in PCPs and in Linearity Tests: Luca Trevisan, MIT.

10:35
The Closure of Monadic NP: Miklós Ajtai, Ronald Fagin, Larry Stockmeyer, IBM.


Session 6B: 10:10am-10:55am
Chair: Fan Chung Graham

10:10
Information Theoretic Implications for Pairing Heaps: Michael L. Fredman, Rutgers.

10:35
Min-Wise Independent Permutations: Andrei Broder, DEC; Moses Charikar, Stanford; Alan Frieze, CMU; Michael Mitzenmacher, DEC.




Invited talk: 11:00 am-12:00 pm
Chair: Milena Mihail

11:00
The Approximability of NP-hard Problems: Sanjeev Arora, Princeton.




Lunch break: 12:00 noon-1:40pm


Session 7A: 1:40pm-3:40pm
Chair: Serge Plotkin

1:40
Algorithms for Capacitated Vehicle Routing: Moses Charikar, Stanford; Samir Khuller, U. of Maryland; Balaji Raghavachari, U. of Texas, Dallas.

2:05
Adaptive Packet Routing for Bursty Adversarial Traffic: William Aiello, Bellcore; Eyal Kushilevitz, Technion; Rafail Ostrovsky, Bellcore; Adi Rosen, U. of Toronto.

2:30
Stability Results for Networks with Input and Output Blocking: Matthew Andrews, Lisa Zhang, Bell Labs.

2:55
Randomized Protocols for Low-Congestion Circuit Routing in Multistage Interconnection Networks: Richard Cole, NYU; Bruce M. Maggs, CMU; Friedhelm Meyer auf der Heide, U. of Paderborn, Germany; Michael Mitzenmacher, DEC; Andrea W. Richa, CMU; Klaus Schroder, U. of Paderborn, Germany; Ramesh K. Sitaraman, U. of Massachusetts; Berthold Voecking, U. of Paderborn, Germany.

3:20
TCP Dynamic Acknowledgment Delay: Theory and Practice: Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott, Washington University.


Session 7B: 1:40pm-3:40pm
Chair: Carsten Lund

1:40
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge: Oded Goldreich, Weizmann; Amit Sahai, Salil Vadhan, MIT.

2:05
Concurrent Zero Knowledge: Cynthia Dwork, IBM; Moni Naor, Weizmann Institute; Amit Sahai, MIT.

2:30
Modular Approach to the Design and Analysis of Key Exchange Protocols: Mihir Bellare, U. C. S. D.; Ran Canetti, IBM; Hugo Krawczyk, Technion.

2:55
A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs: Anna Gál, U. of Texas, Austin.

3:20
Checking Polynomial Identities over any Field: Towards a Derandomization?: Daniel Lewin, Salil Vadhan, MIT.


Break: 3:40pm-4:15pm



RUMP Session: 4:15pm-5:45pm
Chair: Nick Pippenger


Banquet: Buses leave at 6pm
for the Southfork Ranch

TUESDAY, MAY 26


Continental Breakfast: 7:30am-8:15am


Session 8A: 8:15am-9:50am
Chair: S. Muthu Muthukrishnan

8:15
Multicasting in Heterogeneous Networks: Amotz Bar-Noy, Tel Aviv Univ.; Sudipto Guha, Stanford; Joseph (Seffi) Naor, Technion; Baruch Schieber, IBM.

8:40
Minimizing Stall Time in Single and Parallel Disk Systems: Susanne Albers, Naveen Garg, Max-Planck-Institut für Informatik; Stefano Leonardi, Università di Roma.

9:05
On Indexed Data Broadcast: Sanjeev Khanna, Shiyu Zhou, Bell Labs.

9:30
Segmentation Problems: Jon Kleinberg, Cornell; Christos Papadimitriou, Berkeley; Prabhakar Raghavan, IBM.


Session 8B: 8:15am-9:50am
Chair: Ramaramohan Paturi

8:15
Computing Local Dimension of a Semialgebraic Set: Nicolai Vorobjov, Univ. of Bath, England.

8:40
Asymptotic Acceleration of Solving Multivariate Polynomial System of Equations: B. Mourrain, INRIA, France; V. Y. Pan, Lehman College, CUNY.

9:05
A Black Box Approach to the Algebraic Set Decomposition Problem: Ming-Deh A. Huang, Ashwin J. Rao, Univ. of Southern Calif.

9:30
Are Lower Bounds Easier Over the Reals?: Hervé Fournier, Pascal Koiran, Ecole Normale Supérieure de Lyon.


Break: 9:50am-10:25am


Session 9A: 10:25am-12:00 noon
Chair: Serge Plotkin
10:25
Planar Map Graphs: Zhi-Zhong Chen, Tokyo Denki Univ.; Michelangelo Grigni, Emory Univ.; Christos Papadimitriou, Berkeley.

10:50
Further Algorithmic Aspects of the Local Lemma: Michael Molloy, Univ. of Toronto; Bruce Reed, CNRS.

11:15
Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem: Jon M. Kleinberg, Cornell.

11:40
Improved Approximation Schemes for Travleing Salesman Tours: Satish B. Rao, Warren D. Smith, NEC.


Session 9B: 10:25am-12:00 noon
Chair: Russell Impagliazzo

10:25
Finding Almost-Satisfying Assignments: Uri Zwick, Tel Aviv Univ.

10:50
On the Complexity of Unsatisfiability Proofs of Random k-CNF Formulas: Paul Beame, Richard Karp, Univ. of Washington; Mike Saks, Rutgers; Toni Pitassi, Univ. of Arizona.

11:15
k-sat on Groups and Undecidability: Michael H. Freedman, Microsoft.

11:40
An Exponential Lower Bound for Depth 3 Arithmetic Circuits: Dima Grigoriev, Penn State; Marek Karpinski, Univ. of Bonn.


Lunch break: 12:00 noon-1:30pm


Session 10A: 1:30pm-2:40pm
Chair: Michael Kearns

1:30
A New Composition Theorem for Learning Algorithms: Nader H. Bshouty, Univ. of Calgary.

1:55
Adaptive Versus Nonadaptive Attribute-Efficient Learning: Peter Damaschke, Fern Universität, Germany.

2:20
On the Complexity of Protein Folding: Pierluigi Crescenzi, Università di Firenze; Deborah Goldman, Christos Papadimitriou, Berkeley; Antonio Piccolboni, Univ. di Milano; Mihalis Yannakakis, Bell Labs.


Session 10B: 1:30pm-2:40pm
Chair: Tandy Warnow

1:30
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality: Piotr Indyk, Rajeev Motwani, Stanford.

1:55
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces: E. Kushilevitz, Technion; R. Ostrovsky, Bellcore; Y. Rabani, Technion.

2:20
Improved Bounds for Acyclic Job Shop Scheduling: Uriel Feige, Christian Scheidele, Weizmann Institute.


Break: 2:40pm-3:10pm


Session 11A: 3:10pm-3:55pm
Chair: Milena Mihail

3:10
Broadcast Disk Paging: Sanjeev Khanna, Bell Labs; Vincenzo Liberatore, Rutgers.

3:35
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling: Nathan Linial, Alex Samorodnitsky, Avi Wigderson, Hebrew Univ.


Session 11B: 3:10pm-4:20pm
Chair: Ran Raz

3:10
On Separating the Read-k-Times Branching Program Hierarchy: Jayram S. Thathachar, Univ. of Washington.

3:35
Robust Efficient Distributed RSA-Key Generation: Yair Frankel, CertCo; Philip MacKenzie, Boise State Univ.; Moti Yung, CertCo.

4:00
One Help-bit Doesn't Help: Richard Beigel, Lehigh Univ.; Tirza Hirst, Bar Ilan Univ.


End of Symposium: 4:20 pm

General Information


Location:

All conference events except the banquet will take place at the Fairmont Hotel in downtown Dallas, at 1717 North Akard Street. The banquet will be held at the Southfork Ranch, near Dallas (buses will be provided for conference attendees).


Registration:

The registration desk will be open from 6 - 9 pm on Saturday, from 8 am - 5 pm Sunday and Monday, and from 8 am - 2:30 pm Tuesday.


Registration Fee:

The non-student registration fee includes the Saturday night reception, the Sunday night business meeting, the Monday night banquet, coffee breaks, lunches, and a copy of the proceedings. The student fee includes all of the above except the banquet.


Proceedings:

Prepaid additional copies of the STOC'98 proceedings can be ordered with the registration form and will be available for pick-up at registration. There will also be copies available at the registration desk on a first come, first served basis, while supplies last, for $54 per copy.


Hotel Information:

Our block of rooms at the Fairmont Hotel is being held from May 21 until May 29. We encourage you to make your reservations by telephone.

The conference hotel will be the Fairmont Hotel, which is located in the Dallas Arts District. The hotel has a similar ambiance to the renowned Fairmont in San Francisco on Nob Hill. It is a Mobil Four-Star and a AAA Four-Diamond hotel with 24 hour dining. The Pyramid Room has been a consistent recipient of the Travel/Holiday Award for Dining Excellence.


Banquet:

For an authentically fake Dallas experience, the banquet will be held at the Southfork Ranch, the location where the television series ``Dallas'' was filmed in the 80's. This ranch was bought by an investor recently who has turned the place into a convention facility. We will provide Kosher and Vegetarian meals for those who request them on their conference registration form.

Buses will be provided to and from the ranch. Buses leave the hotel at 6 P.M.


Official Airlines:

Continental Airlines is the official airline for STOC 98. We have negotiated substantial reduced fares (zone fares and/or discounted fares) for flights to and from the conference. Call 1-800-468-7022 and mention the locator NNGPZL.


Getting to the Hotel:

Conference attendees traveling by air may arrive at either the Dallas-Fort Worth airport (DFW) or Dallas Love Field, although restrictions placed on flights to and from Love Field make travel there difficult unless you are coming from Texas or a neighboring state.

The ``SuperShuttle'' provides transportation between either airport and the Fairmont Hotel. From DFW airport, after collecting your baggage use the ground transportation board courtesy phone to make arrangements, and a shuttle will then meet you at the Shared Ride Zone on the lower level. The fare from DFW is $11 per passenger. From Love Field, advance scheduled pick-up is available by calling (817) 329-2000; the fare from Love Field is $9 per passenger. If you prefer to take a taxi, the fare from DFW airport to the hotel is approximately $33, and the fare from Love Field is approximately $10.

To get back to the airport from the hotel using the SuperShuttle, advanced reservations are required. More information can be obtained from the hotel.

If you are driving your own car or renting a car at the airport, you can reach the hotel using the following directions.

If you are driving in from the north or the south, take Interstate 35E toward Dallas. Exit on Highway 45/75 to Houston/Sherman, and take the first exit to Griffin Street. Merge left onto Griffin and continue straight to the first stop light, which is Ross Avenue. Turn left on Ross and go two blocks to Akard Street. Take a left on Akard and the Fairmont will be on your immediate left.

If you are coming from DFW airport, take the South exit from the airport and follow road signs to Dallas. This will take you on Highway 183 East to Interstate 35E, which you should take south. From that point you can follow the driving directions given above.

If you are coming from Love Field, go West (right) on Mockingbird Lane after leaving the airport. Mockingbird will take you to I-35E, which you should take south and pick up the driving directions given above.

If you are driving in from the west, take eastbound Interstate 30 and exit to your left on Downtown Business District -- 35E North. From that point go to the Highway 45/75 exit, and follow the directions for driving in from the south.

If you are driving in from the east, take westbound Interstate 30 to the Ervay Street exit which you take from the left-hand lane of I-30. Take a right on Ervay and continue approximately 14 blocks to Ross Avenue. Cross Ross Avenue and the hotel is on your immediate left.

At the hotel, parking is available for $15 per day (short stays may be charged less on an hourly basis). The garage is monitored by security cameras on a 24-hour basis.


Child Care:

Child care can be arranged by the concierge at the hotel.


Climate:

In May, the average high temperature is 82 degrees Fahrenheit (27$^\circ$C) and the average low temperature is 63 degrees Fahrenheit (17$^\circ$C). These Spring-time days can be very nice; however, in Texas we have an expression: ``If you don't like the weather, wait an hour.'' The weather can and does change very quickly here, so you might want to check a forecast before going outside for long periods of time.


Things to Do:

The Fairmont Hotel is in the Arts District of Dallas, and is within a short distance of several interesting areas. Dallas is home to over 160 museums, galleries, and artistic attractions, many within a short distance of the conference hotel. Restaurants are also in abundance: Dallas has more restaurants per capita than New York City (over 6,000 in all!), and includes the only AAA 5-diamond restaurants in all of Texas (The French Room and The Mansion on Turtle Creek).

One block east from the hotel (on Ross Avenue and St. Paul Street) you will find the Dallas Museum of Art, which houses one of the best pre-Columbian art exhibits in the country. A couple of blocks further east (and one block north) will bring you to the Morton H. Myerson Symphony Center, an impressive building designed by noted architect I.M. Pei and begun with a $17 million donation from Ross Perot. Fans of architecture may want to check out Dallas City Hall (1500 Marilla St.), also designed by I.M. Pei.

About four blocks to the west of the hotel you encounter the West End Historic District, a rather touristy area with over 80 shops and 55 restaurants, including largely Texas and Louisiana style food, as well as a brew-pub and a Planet Hollywood. On weekends the West End is a festive area with street mimes, horse and buggy rides, and live entertainment. Also in the West End you will find Dallas Alley, an area with nine nightclubs that can all be visited for one shared cover charge.

A little bit past the West End, you can visit sites dedicated to the most infamous event in Dallas history -- the assasination of John F. Kennedy. Dealley plaza (where the assasination occurred) and the John F. Kennedy Memorial Plaza are both near the west end of Main Street. The Sixth Floor Museum (411 Elm St.) is a permanent educational museum which examines the life, death, and legacy of John F. Kennedy. It is housed in the former Texas School Book Depository, which is where Lee Harvey Oswald was perched to shoot Kennedy. Or maybe not. If you want to explore other possibilities, you can check out the Conspiracy Museum (110 S. Market Street) to learn about the ``other side of the JFK assassination,'' as well as conspiracy theories about the assassinations of Presidents Lincoln and Garfield, Martin Luther King, Jr., and Robert Kennedy. For a more morbid approach, you can take a drive along Kennedy's exact route in a replica of the limosine he was shot in, complete with ``realistic sound effects.''

For a more alternative area, you can head southeast from the hotel (about 10 blocks) to the area known as Deep Ellum, around Elm Street and Central Ave. This eclectic area is home to many night clubs, tattoo parlors, unique shops, and good restaurants. Near that area, you might also want to check out the Majestic Theater, a restored 1920's vaudeville and movie palace that is now home to local performing arts and touring shows.

For an area with still another feel to it, visit the McKinney Avenue area by taking the McKinney Avenue Trolley from St. Paul Street, next to the Dallas Museum of Art. The Trolley is the largest volunteer-run system in the world. McKinney Avenue is an upscale area and is home to many fine restaurants, galleries, and shops, as well as some touristy places like the Hard Rock Cafe.

To get to some locations farther from the hotel, the DART Light Rail is a commuter rail system that is the newest and most modern in the U.S. You can catch this system a couple of blocks from the hotel at the Akard Station (on Pacific Ave. between Akard and Field Street). You can travel within the Central Business District for 50 cents, or outside this area for one dollar. Going north, you can travel to the SMU area (go to the Mockingbird Station). Going south, you can travel to the Dallas Zoo, which is home to over 1,500 animals, including the 25-acre ``Wilds of Africa'' exhibit.

Requiring a short car or a taxi ride, the lower Greenville Avenue area is an interesting blend of restaurants and entertainment. The restaurants are good and (for the most part) reasonably priced, and you can find good American, Mexican, Thai, French, and other types of food here.

A short ride to the east of the hotel takes you to Fair Park, which has 8 museums (including ``Science Place'') and an IMAX theater.

The Dallas Arboretum and Botanical Gardens (8525 Garland Rd.) is a slightly longer drive to the east, and consists of 66 acres, including the largest public collections of azalea in the country.

If you have access to a car, you could consider visiting neighboring Fort Worth. While only a fraction of the size of Dallas, Fort Worth offers some attractions which rival or exceed their counterparts in Dallas. The Kimbell Art Museum (3333 Camp Bowie Blvd) is a small museum, but attracts some of the top traveling exhibits in the world. Other museums in the same general vicinity of Fort Worth include the Amon Carter Museum, the Modern Art Museum, and the Museum of Science and History. Near the museums is the Fort Worth Botanical Gardens, a wonderful place to spend a nice spring day. A short distance from these attractions is the Fort Worth Zoo (1989 Colonial Parkway) -- beautifully managed, it is rated as one of the top five zoos in the country.

More information can be obtained from the STOC'98 World Wide Web page, whose URL is http://sigact.acm.org/stoc98


Program Committee:

Fan Chung Graham (Chair), Russell Impagliazzo, Michael Kearns, Janos Komlos, Carsten Lund, Milena Mihail, S. Muthu Muthukrishnan, Ramamohan Paturi, Nick Pippenger, Serge Plotkin, Ran Raz, Arnold Rosenberg, Subhash Suri, Ramarathnam Venkatesan, Tandy Warnow, Andrew Yao.


Local Committee:

Wolfgang Bein, General Chair, bein@utdallas.edu
Steve Tate, General Chair, srt@cs.unt.edu
Lawrence Larmore, Treasurer
Ian Parberry, Publicity