PROGRAM AND REGISTRATION INFORMATION ISTCS'95 The third Israel Symposium on Theory of Computing and Systems (ISTCS'95) will take place in Tel Aviv, Israel, Jan 4th-6th, 1995. This message includes A) The final program for ISTCS'95. B) General information. C) A 3 part registration form for ISTCS'95: (1) conference registration, (2) hotel reservation form, and (3) excursion registration. Please register (conference, hotel, excursion) by November 25. Also, send a hardcopy to Marganit Charish including the conference registration fee. We ask that you send a check or money order only for the conference registration. Hotels will be paid directly and the excursion fees can be paid at the registration desk. Direct all correspondence to Marganit Charish, Secretary of ISTCS, by e-mail, phone, fax, or AIR MAIL (not 1st class mail!!!) Marganit Charish, Secretary of ISTCS'95 Department of Computer Science School of Mathematical Sciences Tel Aviv University Tel Aviv Israel e-mail: marga@math.tau.ac.il, phone: +972-3-6408040, fax: +972-3-6409357. =================================================================== CONFERENCE PROGRAM ========================= WEDNESDAY, JANUARY 4th, MORNING =============================== 09:00 -- 09:45 Wolfgang Paul (invited talk): High Performance Transaction Systems on the SB-PRAM 09:50 -- 11:05 Session 1 (chair D. Peleg): ------------------------------------------ 09:50-10:15 Improved optimal shared memory simulations, and the power of reconfiguration Artur Czumaj, Friedhelm Meyer auf der Heide and Volker Stemann 10:15-10:40 Randomized single-target hot-potato routing Ishai Ben Aroya, Ilan Newman and Assaf Schuster 10:40-11:05 Observations on hot potato routing Uriel Feige 11:05 -- 11:25 coffee break 11:25 -- 12:40 Session 2 (chair R. Shamir): ------------------------------------------- 11:25-11:50 NP-sets are Co-NP-immune Relative to a Random Oracle Nikolai K. Vereshchagin 11:50-12:15 Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP Nikolai K. Vereshchagin 12:15-12:40 A lower bound on the mod 6 degree of the or function Gabor Tardos and David A. Mix Barrington 12:45 Lunch WEDNESDAY, JANUARY 4th, AFTERNOON ================================= 14:45 -- 15:30 Robert J. Aumann (invited talk): TBA 15:35 -- 16:25 Session 3 (chair S. Klein): ------------------------------------------ 15:35-16:00 A general technique for implementation of efficient priority queues Peter Hoyer 16:00-16:25 All shortest paths in weighted grid graphs and its application to finding all approximate repeats in strings Jeanette P. Schmidt 16:25 -- 16:45 coffee break 16:45 -- 17:35 Session 4 (chair M. Naor): ----------------------------------------- 16:45-17:10 Improved algorithms in geometric optimization via expanders Matthew J. Katz 17:10-17:35 Finding percentile elements Dorit Dor and Uri Zwick WEDNESDAY, JANUARY 4th, EVENING =============================== 18:00-19:00 Business Meeting 20:00-on Reception and Banquet - Tel Aviv Sheraton =================================================================== THURSDAY, JANUARY 5th, MORNING ============================== 09:00 -- 09:45 Abe Peled (invited talk): The electronic global village - challenges and opportunities 09:50 -- 11:05 Session 5 (chair O. Shmueli): ------------------------------------------- 09:50-10:15 Public data structures: counters as a special case Hagit Brit, Shlomo Moran and Gadi Taubenfeld 10:15-10:40 Dynamic counting Amir Ben-Dor, Amos Israeli and Asaf Shirazi 10:40-11:05 Towards a practical snapshot algorithm Yaron Riany, Nir Shavit and Dan Touitou 11:05 -- 11:25 coffee break 11:25 -- 12:40 Session 6 (chair O. Grumberg): --------------------------------------------- 11:25-11:50 A partial order approach to branching time model checking Rob Gerth, Ruurd Kuiper, Doron Peled and Wojciech Penczek 11:50-12:15 More on nonregular PDL: expressive power, finite models, Fibonacci programs David Harel and Eli Singerman 12:15-12:40 Automata with sensing heads H. Petersen 12:45 Lunch THURSDAY, JANUARY 5th, AFTERNOON ================================ 14:45 -- 15:30 (invited paper): Open Problems in Computational Molecular Biology Pavel Pevzner and Michael Waterman 15:35 -- 16:25 Session 7 (chair J. Schmidt): ----------------------------------------- 15:35-16:00 Computation of highly regular nearby points Carsten Rossner and Claus P. Schnorr 16:00-16:25 Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT Uriel Feige and Michel X. Goemans 16:25 -- 16:45 coffee break 16:45 -- 18:00 Session 8 (chair R. Roth): ----------------------------------------- 16:45-17:10 Some improvements to total degree tests Katalin Friedl and Madhu Sudan 17:10-17:35 On the role of shared randomness in two prover proof systems Mihir Bellare, Uriel Feige and Joe Kilian 17:35-18:00 On the complexity of statistical reasoning Joe Kilian and Moni Naor =================================================================== FRIDAY, JANUARY 6th, MORNING ============================ 09:00 -- 09:45 Avi Wigderson (invited talk): Computational Pseudo-randomness 09:50 -- 11:05 Session 9 (chair M. Sharir): -------------------------------------------- 09:50-10:15 Optimal deterministic approximate parallel prefix sums and their applications Tal Goldberg and Uri Zwick 10:15-10:40 On the power of randomization for the common PRAM Omer Berkman, Phillip B. Gibbons and Yossi Matias 10:40-11:05 Randomized on-line scheduling of parallel jobs Jiri Sgall 11:05 -- 11:25 coffee break 11:25 -- 12:40 Session 10 (chair N. Linial): ------------------------------------------- 11:25-11:50 Using approximate agreement to obtain complete disagreement: The output structure of input-free asynchronous computations Shlomo Moran 11:50-12:15 Trade-offs between message delivery and quiesce times in connection management protocols Hagit Attiya, Jon Kleinberg and Nancy Lynch 12:15-12:40 Local computations on static and dynamic graphs Alain Mayer, Moni Naor and Larry Stockmeyer Conference Adjourns. ************************************************************************* CONFERENCE ORGANIZATION Steering Committee: Danny Dolev (Hebrew University); Shimon Even (Technion - Israel Institute of Technology); Zvi Galil (Columbia University and Tel Aviv University); Richard M. Karp (ICSI and UC Berkeley); Michael O. Rabin (Harvard University and Hebrew University); Michael Rodeh (IBM Israel Scientific Center); Arny Rosenberg (University of Massachusetts); Oded Goldreich (The Weizmann Institute). Symposium Chairs: Michael Luby (ICSI and UC Berkeley): luby@icsi.berkeley.edu Uzi Vishkin (University of Maryland and Tel Aviv University): vishkin@umiacs.umd.edu Program and Publication Chair: David Peleg (The Weizmann Institute): peleg@wisdom.weizmann.ac.il Local Arrangements Chair: Amos Fiat (Tel Aviv University): fiat@taurus.math.tau.ac.il Phone: +972-3-6409161 Secretary: Marganit Charish (Tel Aviv University): marga@math.tau.ac.il Phone: +972-3-6408040 ACKNOWLEDGMENTS ISTCS'95 is sponsored by the following organizations and industries: The Foundation for the Promotion of Education in Electronics and Computer Science Technologies (Israel); Scitex Ltd (Israel); Algorithmic Research Ltd (Israel); The Hebrew University; Technion - Israel Institute of Technology; Tel Aviv University; The Weizmann Institute of Science. ISTCS'95 proceedings will be published by the IEEE Computer Society press and ISTCS is held in cooperation with the ACM Special Interest Group on Automata and Computability Theory (SIGACT). =================================================================== GENERAL INFORMATION =================== The conference will be held at Tel Aviv University starting Wednesday morning January 4th, 1995, through Friday noon, January 6th. On Wednesday the conference will hold a business meeting on campus followed by a reception and banquet at the Tel Aviv Sheraton. An excursion to Eilat is offered to the participants, starting Friday noon, January 6th, through Sunday evening, January 8th. Israeli meteorological services multi-year average daytime highs for Tel Aviv in January are 18C (64.5F), nighttime lows 9C (48F), and 64% relative humidity. The probability for some rain during the conference is 0.36. Multi year average rainfall during the entire month of January is 125mm. It is also entirely possible that there will be no clouds in the sky for the entire period. Multi-year average daytime highs for Eilat in January are 21C (70F), nighttime lows 9.5C (49F). Average relative humidity is 45%. The probability of rain is too low to be measured. Multi year average rainfall during the month of January is 5mm, but most years it never rains at all. Accommodations in Tel Aviv are at the Maxim hotel and the Sheraton hotel, both on the Tel Aviv sea front, a 4 minute walk from one to the other. There are many restaurants within a few minutes walk. Both hotels overlook the Mediterranean and have easy access to a sandy beach. The recommended transportation from Ben-Gurion airport to the hotel is by a taxi and it should cost around $15. Alternately, one can take the 222 airport bus that leaves every half hour in the morning, every hour in the afternoon. The 222 bus stops at all hotels on the Tel Aviv sea front, the fare is approximately $2. Talks will be held at the Schreiber Math building, near gate 2 of the university. Gate 2 is a walk-in gate and is also used to reach the "Diaspora House", a world-class museum of Jewish history. The simplest way to reach the campus from the hotel is via taxi, such a ride should cost about $5. Alternately, a 10 minute walk due east to King George st. and the #25 bus will get you to campus at a cost of less than $1. The registration desk will open during the day on Wednesday, January 4th and Thursday January 5th. Additional copies of the proceedings will be sold on Wednesday through Thursday at the registration desk. Registration has 3 parts, conference, hotel, and excursion. Please fill in the applicable sections, send via e-mail to Marganit Charish, and send a hardcopy via AIR MAIL including the conference registration fee. Do NOT send a check for the hotel nor for the excursion fee. Please register soon. The excursion may be cancelled if there is insufficient interest by December 1st. Financial support: Some VERY limited financial support and/or a waiver of the registration fees may be available for students and others with limited funding. If you require financial support, send e-mail to the ISTCS secretary. =================================================================== ****************** CUT HERE ************************** Registration for ISTCS'95 Conference: January 4th - January 6th 1995 Hotels in Tel Aviv Eilat Excursion: January 6th - January 8th 1995 Send via e-mail to marga@math.tau.ac.il Also, send hardcopy to Marganit Charish, Secretary of ISTCS'95 Department of Computer Science School of Mathematical Sciences Tel Aviv University Tel Aviv Israel _________________________ PART 0. Personal Details: _________________________ Name: Affiliation: Street Address: City, State: Country: ZIP or postal code: E-mail: Phone: FAX: _______________________________ PART 1: Conference registration _______________________________ The conference registration fees for ISTCS'95 include a reception and banquet on Wednesday night, coffee breaks, two lunches, and a copy of the proceedings. Register by e-mail, and use AIR MAIL (not first class mail) to send hardcopy registration form, along with check or money order for the conference registration fee, payable to "ISTCS'95". Please circle the appropriate entries below. Early registration (Hardcopy registration and conference registration fee sent by November 25th): Student $50 (120 NIS), Other $130 (390 NIS) Late registration (Conference registration fee sent after November 25th): Student $70 (150 NIS), Other $160 (480 NIS) Extra banquet tickets $40/each. Number of extra banquet tickets:__. _______________________________ PART 2: Hotel reservations: _______________________________ Two hotels are available. They are very close to each other. The banquet will be held at the Sheraton Hotel. The Maxim Hotel is not fancy and may be somewhat noisy, however, it is is used regularly by Tel Aviv University to accommodate faculty guests and we have had very good experience with it. To make your reservation please fill out the following details and send it along with the conference registration form. Please send an e-mail copy of this registration form AND a hardcopy. Payment is made directly to the hotel but please remember that the conference is responsible for room orders. If you wish to cancel after you've registered, please let us know ASAP via e-mail. Please circle the appropriate entries below. A. No hotel reservations required. B. Maxim Hotel: All rooms are "large" (double): Single occupancy Double occupancy front: (facing Med.): $53. /day $64 / day (only 4 such rooms register early!!!, May be somewhat noisy) side: (can see Med.): $51. /day $62 / day C. Sheraton Hotel: Single room: $166. /day (includes 15% "service charge") Double room: $196. /day (includes 15% "service charge") Please fill out: Arrival Date: Departure Date: If you want to attend the Eilat excursion (or some other travel arrangements) and then return to the hotel, please give us 2nd period: 2nd Arrival Date: 2nd Departure Date: Sharing room with ________________ (if you need help in finding a room mate please let the ISTCS secretary know and we will do our best): _______________________________ PART 3: Eilat Excursion: _______________________________ Eilat is now very much in the news as the apex of the "Peace triangle", 30 minutes to Taba Egypt and its casino(s), 30 minutes to Aqaba, Jordan, and its restaurants. It is now possible to visit both from Eilat. However, the main attraction is the red sea and its corals. The red sea is one of the 3 major diving sites in the world. Eilat itself has much to offer with day and night desert tours, nighttime activities, restaurants, etc. It is very easy to take an introductory scuba lesson and to view the red sea from 100 meters below the surface in a yellow submarine. The excursion leaves Friday afternoon, at 3:30PM, (January 6th) from Sde-Dov, the local Tel Aviv airport - 10 minutes by taxi from the campus and hotels. Returning Sunday evening, at 7:00PM, (January 8th) arriving Ben-Gurion airport. We stay two nights at the Reef hotel, next door to the Aqua sport international diving center, the Eilat Club Med., and the "last refuge" fish restaurant. Hotel rooms actually overlook the red sea. It is a 5 minute walk to the entrance of the Eilat coral reserve where one can spend all day snorkeling and scuba diving. A 10 minute walk takes you to the Eilat underwater observatory where one can observe the corals and fish of the red sea without getting wet. You can make some changes in the plans, stay longer in Eilat, etc. You can fly from Eilat back to Sde-Dov at an added cost of 30IS or fly to Eilat from Ben-Gurion at a discount of 30IS. Rates (includes round trip air fare, hotel stay, and transportation to and from the hotel and airport in Eilat): Single room: 842 IS. (about 3.0IS = $1). Double room double occupancy: 701 IS/person. These rates are about 20% less than the normal rates. Please circle: 1) Single room. 2) Double room for two. (At 701IS/person). 3) Want to share double room with _____________ (if you need help in finding a roommate for the excursion, please let the ISTCS secretary know and we will do our best): _______________________________ SIGNATURE: *************** CUT HERE ***********************************************