The Twenty-seventh Annual ACM Symposium on Theory of Computing (STOC), sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory), was held in Las Vegas, Nevada, May 29-June 1, 1995. A printable version of the preliminary hardcopy announcement (including registration forms) is available in postscript and plaintext formats.

A participant list is available.

STOC 95 is notable as the first STOC conference to accept electronic submissions. More information is available on how this was done.



The conference will be held in the Island Tower of the Tropicana Hotel. The Island tower has its own entrance, is adjacent to parking, has no gambling, and is connected by a bridge over the lagoon area to the Paradise Tower where the main casino is located.

The Tropicana Hotel.

The Tropicana Hotel is at the South-East corner of Four Corners (also called South Strip.) Four newly constructed pedestrian bridges carry foot traffic across Las Vegas Blvd. and Tropicana Ave, connecting the 6 hotels (15,000 rooms) of Four Corners. Directly East is the mighty MGM grand, with 5000 rooms the largest hotel in the world. Directly West is the fabulous Excalibur, with 4000 rooms the second-largest hotel in the world. Needless to say, there are many alternate hotels close by the conference site.

DISCLAIMER: All prices for accommodation are not necessarily current. Please call the hotels for up-to-date information.

Also available:

Hotel Reservations

Deadline: Friday, April 28, 1995

The rates for STOC '95 are posted below and apply from May 26 to June 4.

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

To make reservations by phone, call 702-739-2222, 800-634-4000 or 800-GO-2-TROP, fax 702-739-2469. To make reservations, fill out the reservation form and fax it or mail it to the following address.

Tropicana Hotel
ATTN: STOC'95 registration
Tropicana Avenue at Las Vegas Boulevard
Las Vegas NV
Credit card information or a deposit (in the form of a check or money order for one night's stay made payable to the Tropicana Hotel) must be included. Deposits will be refunded if the hotel is notified prior to 48 hours before arrival.

Rate (Sunday-Thursday): $75 plus tax for a single or double room, $90 for a triple room.

Weekend rates (Friday-Saturday): $95 plus tax for a single, double, or triple room.

Registration Information


To qualify for the early registration fee, your registration application must be postmarked by Monday, May 1, 1995. Refund requests will be honored until May 8, 1995. The registration fee includes the Monday night reception, the Tuesday night business meeting, coffee breaks, lunches, and a copy of the proceedings. Send the registration form along with a check or money order in U.S. currency made payable to STOC '95, to:
Department of Computer Science
University of Nevada
Las Vegas NV 89154-4019

On-Site Registration

The registration desk in the Foyer will be open from 6-8 pm on Monday, from 7:30 10:30 am Tuesday through Thursday, and from 3-5 pm Tuesday and Wednesday.

Conference Program

The conference brochure, which includes the program, registration forms, and conference information, is available in the following formats:


The reception is the night of Monday, May 29 (Memorial day). The talks are Tuesday, May 30 through Thursday, June 1. On the night of Wednesday, May 31, as a substitute for a banquet, those who sign up will get a medieval show at the Excalibur, with dinner (rock game hen) eaten with fingers (more details below).

Child Care

Hotel room child care is available 24 hours through Vegas Valley Babysitting at 871-5161. The minimum charge is $34 for 2 children for 4 hours. Call to get other rates. Arrange at least 8 hours in advance.


Official Airline

American Airlines has been appointed the official air carrier for STOC '95. When calling for reservations, be sure to mention the Star File number NBR-S0455MA and refer to our event as ``STOC.'' Telephone 800-433-1790.

Getting to Las Vegas and the Hotel

Access to Las Vegas is through McCarren International Airport, only 2 miles from the Tropicana Hotel. Taxi Fare is approximately $8. The Gray Line Shuttle costs $3.75.

If you plan to travel anywhere in Las Vegas other than along the Strip, or to Lake Mead or the mountains, it is necessary to have a car. Rentals are readily available.


The day-time temperature in Las Vegas at the end of May varies between 70 and 90 degrees Fahrenheit. Night-time temperatures are as much as 30 degrees lower. The humidity is very low, and rain is unlikely. But why take our word for it? For more details, you can consult the:


In lieu of the usual banquet, STOC 95 will arrange for participants to attend on the night of Wednesday, May 31 the fabulous King Arthur's Tournament, a medieval-style dinner show featuring knights, jousting, magic, and treachery. (The show is "family," in case you wish to bring the children.) Serving wenches and lackeys will bring your medieval style dinner, which you eat with your fingers. Cheer for your knight. If he gets beaten, it's a shame.

Those who order advance tickets with their registration will be seated in a preferred section along with other STOC participants. There is no way to ask for a specific section if tickets are purchased individually. If you want tickets, check the appropriate box on the registration form. Children under the age of 4 are free, but must sit on an adult's lap and will not be served an extra meal. Kosher meals are available with advance notice (check box). Vegetarian meals are available with no advance notice.

Showtime is 8:30. From the front entrance of the Tropicana Hotel (near the Easter Island Heads), cross Las Vegas Boulevard on the pedestrian skywalk. Enter the fabulous Excalibur through the main portcullis, descend the grand staircase to the Fantasy Faire level, then look for King Arthur's Arena.

Or, arrive early, and spend some time with the shops and free shows every 30 minutes on the Jester Stage of the Medieval Village level. Take the escalator in the middle of the casino floor up to the Medieval Village.


There is no official excursion associated with STOC 95. However, here are some ideas for attendees who arrive early.

River Rafting

Black Canyon River Raft Tours 702-293-3776x204. Tour leaves the Expedition Depot in Boulder City (22 miles from LV) every morning at 9:30. Trip is 3 hours and costs $65/person. Longer raft trips are available also, including some of several days.

Grand Canyon Fly-Over

Scenic Airlines departs from a depot which is actually less than half a mile from the Tropicana. The cheapest overflight costs under $100/person. 702-739-1900.

Other Conferences and Workshops at UNLV

The Second Annual Workshop on Self-Stabilizing Systems will be held May 28-29 on the UNLV campus.

Author Notification

Authors will be notified of acceptance or rejection by February 6, 1995. A camera-ready copy of each accepted paper is required by March 21, 1995, which is firm deadline. One author of each accepted paper should attend the conference and present the paper.

Best Student Paper Award

A prize of $500 will be given to the author(s) of the best student-authored paper (or split between more than one paper if there is a tie). A paper is eligible if all its authors are full-time students at the time of submission.


Prepaid additional copies of the STOC'95 proceedings can be ordered at 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 $60 per copy.

Program Committee

Program Committee Chair

Allan Borodin, University of Toronto (

Committee Members

Conference Committee

Conference Chair and Local Arrangements Chair

Lawrence L. Larmore
Department of Computer Science
University of Nevada at Las Vegas
P.O. Box 454019
Las Vegas, Nevada, 89154-4019


Wolfgang Bein, University of Texas at Dallas (

Publicity Chair

Ian Parberry, University of North Texas.

Registration Co-Chairs

On-Site Registration

Created by Ian Parberry, December 9, 1994.