PROGRAM AND REGISTRATION INFORMATION
ISTCS '96
URL: http://www.cs.rice.edu/~vardi/istcs/
The fourth Israel Symposium on the Theory of Computing and Systems
(ISTCS'96) will take place in Jerusalem, Israel, June 10th-12th, 1996.
This message includes:
1. The final program for ISTCS'96;
2. General information;
3. A 4-part registration form for ISTCS'96:
a. Conference registration;
b. Hotel reservation;
c. Banquet and business meeting registration;
d. Excursion registration.
Please register via e-mail (conference, hotel, excursion) by May 26th.
We ask that you pay by one of the following ways: international money
order, cashier's check, traveler's check, or a Israeli check, for the
conference registration. The registration fee can be paid upon
arrival. Accommodation will be paid directly to the hotel, and the
excursion is covered by the registration fee.
Direct all correspondence to Ruth Cohen (ruta@cs.huji.ac.il),
Secretary of ISTCS, by e-mail, phone, fax, or AIR MAIL:
Ruth Cohen, Secretary of ISTCS '96
Institute of Computer Science
Hebrew University
Jerusalem
Israel
e-mail: ruta@cs.huji.ac.il
phone: +972-2-6584949 (Alt. 6584117)
fax: +972-2-6585439
The Symposium will be part of the new Israeli Federated Computing
Conference (IFCC). The IFCC will include also the 7th Israeli
Conference on Computer-Based Systems and Software Engineering (CBSSE)
(see http://www.cs.huji.ac.il/misc/cbsse/general.html), which will
take place on June 12-13, 1996, a Computer Science Forum at Bar Ilan
University on June 9, 1996(http://www.cs.biu.ac.il:8080/csforum.html)
the 2nd International Workshop on Intelligent Scheduling of Robots
(WISOR), which will take place in Holon on June 6, 1996, and a
Workshop on Real Time and Fault Tolerant Systems, which will
take place at Bar Ilan University on June 16, 1996
(http://www.cs.biu.ac.il/~koren/cswork.html).
===================================================================
CONFERENCE PROGRAM
=========================
Monday, June 10, 1996
_____________________
10:00am - 11:00: Session 1 (Chair: E. Shamir)
Invited Talk: How to Pick a Winner Almost Every Time -- Provably-Good
Algorithms for Decision Making in the Face of Uncertainty
--- Tom Leighton
11:00am - 11:20am: Coffee Break
11:20am - 1:00pm: Session 2 (Chair: S. Plotkin)
On the Borowsky-Gafni simulation algorithm
--- N. Lynch, S. Rajsbaum
Symmetry breaking in anonymous networks: characterizations
--- P. Boldi, B. Codenotti, P. Gemmell, S. Shammah, J. Simon,
S. Vigna
Baked potato routing
--- S. Dolev, E. Kranakis, D. Krizanc
Packet routing via min-cost circuit routing
--- B. Awerbuch, Y. Azar, A. Fiat
1:00pm - 2:30pm: Lunch Break
2:30pm - 3:30pm: Session 3 (Chair: S. Even)
Invited talk: Arrangements of Curves and Surfaces in
Computational Geometry
--- M. Sharir
3:30pm - 3:50pm: Coffee Break
3:50pm - 5:30pm: Session 4 (Chair: Y. Naor)
On advances in optical computational models and problems
which they help to solve
--- Y.B. Karasik
On the hardness of approximating max k-cut and its dual
--- V. Kann, S. Khanna, J. Lagergren, A. Panconesi
To weight or not to weight: where is the question?
--- P. Crescenzi, R. Silvestri, L. Trevisan
Approximating minimum subset feedback sets in undirected graphs
with applications
--- G. Even, J. Naor, B. Schieber, L. Zosin
Tuesday, June 11, 1996
______________________
9:00am - 10:00am: Session 5 (Chair: M.Y. Vardi)
Invited Talk: Visual object recognition,
--- S. Ullman
10:00am - 10:20am: Coffee Break
10:20am - 12:25pm: Session 6 (Chair: A. Rosenberg)
Making the original scoreboard mechanism deadlock free
--- S. Muller, W. Paul
Feasibility and unfeasibility of off-line processing
--- M. Cadoli, F. Donini, P. Liberatore, M. Schaerf
Generalized submodular cover problems and applications
--- J. Bar-Ilan, G. Kortsarz, D. Peleg
On chromatic sums and distributed resource allocation
--- A. Bar-Noy, H. Shachnai, T. Tamir
On the indecomposibility of certain language classes
--- S.W. Margolis, M.V. Sapir, P. Weil
12:25pm - 2:00pm: Lunch Break
2:00pm - 3:15pm: Session 7 (Chair: M.Y. Vardi)
Type dependencies for logic programs using ACI-unification
--- M. Codish, V. Lagoon
Reduction-free normalization for a polymorphic system
--- T. Altenkirch, M. Hofmann, T. Streicher
Updating nonmonotonic databases
--- C. Witteveen, W. van der Hoek
3:15pm - 3:45pm: Coffee Break
3:45pm - 5:25pm: Session 8 (Chair: U. Feige)
On the parallel computation of Boolean functions on unrelated
inputs
--- A. Andreev, A. Clementi, J. Rolim
On satisfiability
--- R. Zippel
On learning conjunctions with malicious noise
--- Y. Mansour, M. Parnas
On the decisional complexity of problems over the reals
--- M. Naor, S. Ruah
6:00pm - Business meeting, reception, and banquet
Wednesday, June 12, 1996
________________________
9:00am - 10:00am: Session 9 (Chair: B. Chor)
Invited Talk: The Airline Crew Pairing Optimization Problem
--- W. Pulleyblank
10:00am - 10:30am: Coffee Break
10:30am - 12:35am: Session 10 (Chair: S. Kutten)
On privacy and partition arguments
--- B. Chor, Y. Ishai
Physical maps and interval sandwich problems: bounded degrees help
--- H. Kaplan, R. Shamir
A new NC algorithm for perfect matching in bipartite cubic graphs
--- R. Sharan, A. Wigderson
Deterministic approximation of the cover time
--- U. Feige, Y. Rabinovich
Smell as a computational resource - a lesson we can learn
from the ant
--- I.A. Wagner, M. Lindenbaum, A.M. Bruckstein
Conference Adjourns.
Excursion - the rest of the day
***********************************************************************
INVITED TALKS
How to Pick a Winner Almost Every Time --
Provably-Good Algorithms for Decision Making in the Face of Uncertainty,
F. Thomson Leighton, MIT
In the talk, we consider a class of problems in which a decision-maker
is required to select from among numerous dividend-paying commodities.
The goal of the decision-maker is to select that commodity (or set of
commodities) that will have the best future return. The task is made
difficult by the constraint that the decision-maker has no way to
predict the future performance of any of the commodities. Somewhat
surprisingly, we will find that the decision-maker can still (at least
in several interesting scenarios) pick a winner with high probability.
Such decision-making problems arise in a variety of contexts,
particularly in the domain of resource allocation. For example, in
the talk, we will describe good algorithms for scheduling jobs on a
network of workstations when very little is known about the future
speed or availability of each workstation. In this problem, the goal
is to schedule each job on a workstation which will have enough
available capacity to complete the job within a reasonable or
specified amount of time. This task is complicated by the fact that
any particular workstation might become saturated by higher-priority
jobs shortly after one of our jobs is assigned to it, in which case
progress will not be made on our job. Thus, in order to complete the
jobs within a specified amount of time, we need to be able to
accurately guess (or predict) which workstations will be available and
when. Somewhat surprisingly, it is possible to make such guesses with
a very high degree of accuracy, even though very little is assumed
about the future availability of the workstations.
The talk will be introductory in nature and represents recent joint
work with Baruch Awerbuch, Yossi Azar, and Amos Fiat.
Biographical Sketch:
Tom Leighton was born in Washington DC, in 1956. He received the
B.S.E. degree in Electrical Engineering and Computer Science from
Princeton University in 1978, and the Ph.D. degree in Applied
Mathematics from MIT in 1981.
Leighton was a Bantrell Postdoctoral Research Fellow at the MIT
Laboratory for Computer Science from 1981 to 1983, and he joined the
MIT faculty as an Assistant Professor of Applied Mathematics in
1982. He is currently a Professor of Applied Mathematics at MIT
and Head of the LCS Theory Group at MIT.
Leighton has published numerous research papers in the areas of
parallel algorithms and architectures, VLSI computation and design,
combinatorial and probabilistic methods, sequential algorithms, and
graph theory. He is the author of two books, including a leading text
on parallel algorithms and architectures. He is a co-inventor on
several patents in network architecture and digital security.
Leighton is the editor-in-chief of the JACM and he serves on seven
other editorial boards. He was recently elected ACM SIGACT Chair, and
he serves on several conference, government, and technical committees.
Dr. Leighton is also a consultant for AT&T, BellCORE, NEC Research,
PWS, Polaroid, and the Government. He was also the co-founder and first
conference chair of the ACM Symposium on Parallel Algorithms and
Architectures, now the leading conference in the area of parallel
algorithms and architectures.
The Airline Crew Pairing Optimization Problem, William R. Pulleyblank,
IBM Thomas J. Watson Research Center
The airline crew pairing problem has received considerable attention
recently as a case of a very large discrete optimization problem which
can be "solved" reasonably efficiently in practice.
We describe the models and methodologies used on this problem, as well
as some of the architectural issues. We also present results recently
obtained using a system jointly developed by IBM Research and Sabre
Decision Technologies, which have reduced the penalty incurred in the
schedule of a major US carrier from a range of 10 to 15 percent
of the base crew cost to approximately 6 percent.
We also discuss some of the areas which we believe offer the greatest
potential for improvement, both in quality of solution and in running
time.
Biographical Sketch:
William R. Pulleyblank is the Director of Mathematical Sciences
at the IBM Thomas J. Watson Research Center in Yorktown Heights,
New York. Before joining IBM in 1990, he was the holder of the
Canadian Pacific Rail - N.S.E.R.C. Chair in Optimization and Computer
Applications at the University of Waterloo, Canada, where he had been
a faculty member since 1982. He is an author or coauthor of more than
fifty research papers, plus TRAVEL, a software product for the PC.
He has consulted on a number of operations research problems.
He has served as an editor of Mathematical Programming, The Journal of
Combinatorial Theory, Series B, and the SIAM Journal on Discrete
Mathematics. His research interests include discrete and combinatorial
optimization as well as applications to practical problems. He has
consulted with such companies as CP Rail, Statistics Canada, Mobil
Oil and Marks and Spencer.
Arrangements of Curves and Surfaces in Computational Geometry,
Micha Sharir, Tel Aviv University
We survey recent progress on combinatorial and algorithmic problems
involving various portions of arrangements of $n$ algebraic surfaces
of constant maximum degree in d>2 dimensions. (Informally, such an
arrangement is the subdivision of space induced by the given
surfaces.) Arrangements of this kind are a central construct in
computational geometry, and arise in many applications, such as motion
planning in robotics, ray shooting and visibility in three dimensions,
Voronoi diagrams, geometric optimization, and more. In these
applications, we are interested not in the full arrangement (whose
complexity is in general O(n^d)) but in various portions, such as the
lower or upper envelope of the surfaces, a single cell of the
arrangement, a "zone" of another surface, etc.
To show that such portions have smaller combinatorial complexity, has
been a major open problem for nearly a decade, ever since analogous
results have been obtained for 2-dimensional arrangements, using the
theory of Davenport-Schinzel sequences (which we will also briefly
review). Considerable progress has been made in the past 3-4 years,
where almost tight bounds (close to O(n^{d-1})) for the complexity of
such arrangement portions have been obtained, including many related
combinatorial and algorithmic results. In the talk we will survey
these recent developments, and present some combinatorial and
algorithmic applications of the new bounds.
Biographical sketch:
Micha Sharir is a Nizri Professor of Computational Geometry and
Robotics in the Department of Computer Science at the School of
Mathematical Sciences of Tel Aviv University. He received his Ph.D.
in Mathematics from Tel Aviv University in 1976. His research
interests include computational and combinatorial geometry and their
applications, motion planning, and other topics in robotics. He is an
author of over 200 research papers, and is also a co-author of the
recent book "Davenport-Schinzel Sequences and Their Geometric
Applications". He is a Visiting Research Professor at the Courant
Institute of Mathematical Sciences, New York University, where he was
also an Associate Director of the Robotics Lab. He was awarded a
Max-Planck Research Prize (jointly with Emo Welzl) in 1992, and an
Honorary Doctorate from the University of Utrecht in 1996. He is the
Director of a newly established Minerva Center in Geometry at Tel Aviv
University.
Visual Object Recognition,
Shimon Ullman, Weizmann Institute of Science
For biological visual systems, visual object recognition is a
spontaneous, natural activity. In contrast, the recognition of common
objects is still way beyond the capabilities of current computer
vision systems. The major difficulty in performing recognition comes
from the fact that the same three-dimensional object can have many
different views, depending on such factors as the viewing direction,
illumination conditions, and partial occlusion by other objects. The
visual system must compensate for these effects in the course of
matching a novel view with object representations stored in memory.
The talk will discuss the main difficulties behind the task of visual
object recognition, and describe an approach to recognition, that uses
the combination of a small number of object views. By using
appropriate combinations, it is possible to generalize to novel
viewing positions and illumination directions under a wide range of
conditions. Some open problems and directions for future studies will
be briefly discussed.
Biographical sketch:
Shimon Ullman is the Samy and Ruth Cohn Professor of Computer Science
at the Weizmann Institute of Science, Rehovot, Israel, where he chairs
the Department of Applied Mathematics and Computer Science. Ullman
studied Mathematics at the Hebrew University in Jerusalem and obtained
his Ph.D. at MIT in 1977. His main field of research is the
computational study of visual perception. Ullman's work includes the
study of motion perception, object recognition, and the modeling of
information processing in the visual cortex. He is the author of "The
Interpretation of Visual Motion", MIT Press, 1979, and "High-level
Vision ", MIT Press, 1996 (to appear).
***********************************************************************
CONFERENCE ORGANIZATION
Steering Committee:
Danny Dolev (The Hebrew University)
Shimon Even (Technion)
Zvi Galil (Columbia University and Tel Aviv University)
Oded Goldreich (Weizmann Institute)
Richard M. Karp (University of Washington)
Michael Luby (ICSI and UC Berkeley)
David Peleg (Weizmann Institute)
Michael O. Rabin (Harvard University and Hebrew University)
Michael Rodeh (IBM Haifa Research Lab)
Arny Rosenberg (University of Massachusetts)
Eli Shamir (The Hebrew University)
Moshe Y. Vardi (Rice University)
Uzi Vishkin (University of Maryland and Tel Aviv University)
IFFC Steering Committee:
Danny Dolev (The Hebrew University)
Zvi Galil (Columbia University and Tel Aviv University)
Martin Golumbic (Bar Ilan University)
Ron Pinter (IBM Haifa Research Lab)
Michael Rodeh (IBM Haifa Research Lab)
Eli Shamir (The Hebrew University)
Moshe Y. Vardi (Rice University)
Michael Winokur (Israeli Aircraft Industry)
Symposium Co-Chairs:
Eli Shamir (The Hebrew University)
shamir@cs.huji.ac.il
Moshe Y. Vardi (Rice University)
vardi@cs.rice.edu
Program Chair:
Moshe Y. Vardi (Rice University):
vardi@cs.rice.edu
Local Arrangements Chair:
Danny Dolev (The Hebrew University):
dolev@cs.huji.ac.il
Secretary:
Ruth Cohen (The Hebrew University):
ruta@cs.huji.ac.il Phone: +972-2-658-4949
Contact List:
Bar Ilan CS Forum: Martin Golumbic
CBSSE - Michael Winokur
IFFC - Michael Rodeh
ISTCS - Moshe Y. Vardi
WISOR - Eugene Levner
ACKNOWLEDGMENTS
ISTCS'96 is sponsored by the following organizations:
Algorithmic Research Ltd (Israel);
Bar Ilan University;
The Hebrew University;
IBM Israel;
Motorola Israel;
News DataCom;
Rice University;
Technion;
Tel Aviv University;
Weizmann Institute of Science;
Leibniz Center for Research in Computer Science
(Hebrew University of Jerusalem)
ISTCS'96 is done in cooperation with the IEEE Computer Society,
Israel Section. ISTCS'96 proceedings will be published by the
IEEE Computer Society Press.
===================================================================
GENERAL INFORMATION
===================
The conference will be held at the Givat Ram campus of the Hebrew
University, Beit Belgia (Belgium House), starting Monday morning
June 10th, 1996, through Wednesday noon, June 12th. On Tuesday,
June 11th, the conference will hold a business meeting followed by
a reception and banquet An excursion in Jerusalem is offered to the
participants, starting Wednesday noon, June 12th, throughout the
rest of the day. The excursion topic is "The importance of Jerusalem
to the three major faiths."
Israeli Meteorological Service's multi-year average daytime highs for
Jerusalem in June is 17-27 Centigrade (63-81 F), with virtually no
chance of rain.
Jerusalem is the capital of Israel. For information about the city
please connect to http://www1.huji.ac.il/jeru/jerusalem.html.
========
Accommodations:
A block of rooms at a special rate was reserved at The Park Plaza
Hotel, on Wolfson St., Jerusalem (located near the entrance to
Jerusalem) and is very close to the Givat Ram campus. Price is
$55/single room, $77/double room (+ VAT for residents of Israel).
Transportation:
The recommended transportation from Ben-Gurion airport to the hotel is
by a taxi. The fare for a shared taxi ("sherut"") is around $10 and
for a one-passenger taxi ("special") around $40. Alternatively, one
can take airport bus no. 111, which leaves every half hour in
the morning and every hour in the afternoon. Bus no. 111 stops at
all major hotels in Jerusalem; the fare is approximately $2.
Talks will be held at Beit Belgia (Belgium House), near the Computer
Science building. It is a walking distance from the main gate and
a short walk from the hotel to the campus.
The registration desk will open during the day throughout the
conference. Additional copies of the proceedings will be sold at
the registration desk.
Registration has 4 parts: conference, banquet, excursion, and hotel.
Please fill in the applicable sections and send via e-mail to Ruth
Cohen. Conference registration can be paid at the registration desk
upon arrival (sorry, no credit cards). Do NOT send a check for the
hotel.
Please register soon!!!!
Students will be admitted free. Student's rate is for those who want
to attend the meals. Extra proceedings will be distributed among the
attended students after the conference (with priority to Ph.D.
students).
===================================================================
Registration for ISTCS'96
Conference: June 10th - June 12th 1996
Send via:
e-mail to ruta@cs.huji.ac.il
fax to 972-2-658-5439
MAILING ADDRESS:
Ruth Cohen, Secretary of ISTCS'95
Institute of Computer Science
The Hebrew University
Jerusalem
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'96 include a reception and
banquet on Tuesday night, coffee breaks, three lunches, a copy of
the proceedings, and the excursion.
Register by e-mail. Registration fee can be paid by international
money order,cashier's check, traveler's checks or a Israeli check,
payable to "ISTCS'96". Fee can be paid upon arrival.
Please mark the appropriate entries below.
___ Registration Fee: $100 (360 NIS)(*NOTE: This is NOT for students.
Students, please see below):
STUDENTS
___ Free (without meals).
___ With meals (3 lunches - $28 (NIS 84), 1 lunch - $10 (NIS 30)).
___ Banquet tickets - $15 each (NIS 48).
___ Excursion fee - $7 (NIS 20).
___ ENTIRE PACKAGE (MEALS, BANQUET, EXCURSION) - $50 (NIS 150).
_______________________________
PART 2: Hotel reservations:
_______________________________
The Park Plaza Hotel, on Wolfson St., Jerusalem (located near the
entrance to Jerusalem) is very close to the Givat Ram campus. Price
is $55/single room, $77/double room (+ VAT for resident of Israel).
Tel. +972-2-6528221, Fax +972-2-6528423.
Please register early, since the number of rooms at this special rate
is limited. The conference secretary will handle the registration.
Please fill out (only for hotel reservation):
Arrival Date: __________________________
Departure Date:__________________________
- - ---------------------------------
PART 3: Banquet and business meeting registration:
- - --------------------------------
On Tuesday 11/6/96 at 6:00pm, a banquet and business meeting will be held
in the Beit Belgia gardens.
Please fill out:
___ I plan to attend the banquet.
___ I do not plan to attend the banquet.
- - ---------------------------------
PART 4: Excursion registration:
- - ---------------------------------
On Wednesday 12/6/96 at 2:00pm (after lunch), there will be a tour of
Jerusalem until approximately 6:00pm. The subject of the tour will be:
The importance of Jerusalem to the three major faiths. The tour will
be led by a professional guide.
Please fill out:
___ I plan to attend the excursion.
___ I do not plan to attend the excursion.
Full Name:____________________________________
Date: ____________________________________