Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, Jerusalem, Israel, June 10-12, 1996, Proceedings. IEEE Computer Society, 1996, ISBN 0-8186-7610-8

Session 1 - Invited Talk

• 
  Frank Thomson Leighton: How to Pick a Winner Almost Every Time: Provably-Good Algorithms for Decision Making in the Face of Uncertainty. 2

Session 2

• 
  Nancy A. Lynch, Sergio Rajsbaum: On the Borowsky-Gafni Simulation Algorithm. 4-15
• 
  Paolo Boldi, Shella Shammah, Sebastiano Vigna, Bruno Codenotti, Peter Gemmell, Janos Simon: Symmetry Breaking in Anonymous Networks: Characterizations. 16-26
• 
  Shlomi Dolev, Evangelos Kranakis, Danny Krizanc: Baked Potato Routing. 27-36
• 
  Baruch Awerbuch, Yossi Azar, Amos Fiat: Packet Routing via Min-Cost Circuit Routing. 37-42

Session 3 - Invited Talk

• 
  Micha Sharir: Arrangements of Curves and Surfaces in Computational Geometry. 44-50

Session 4

• 
  Y. B. Karasik: On Advances in Optical Computational Models and Problems which They Help to Solve. 52-60
• 
  Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi: On the Hardness of Approximating Max k-Cut and Its Dual. 61-67
• 
  Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan: To Weight or Not to Weight: Where is the Question? 68-77
• 
  Guy Even, Joseph Naor, Baruch Schieber, Leonid Zosin: Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications. 78-88

Session 5 - Invited Talk

• 
  Shimon Ullman: Visual Object Recognition. 90

Session 6

• 
  Silvia M. Müller, Wolfgang J. Paul: Making the Original Scoreboard Mechanism Deadlock Free. 92-99
• 
  Marco Cadoli, Francesco M. Donini, Paolo Liberatore, Marco Schaerf: Feasibility and Unfeasibility of Off-Line Processing. 100-109
• 
  Judit Bar-Ilan, Guy Kortsarz, David Peleg: Generalized Submodular Cover Problems and Applications. 110-118
• 
  Amotz Bar-Noy, Hadas Shachnai, Tami Tamir: On Chromatic Sums and Distributed Resource Allocation. 119-128
• 
  Stuart W. Margolis, Mark V. Sapir, Pascal Weil: On the Indecomposibility of Certain Language Classes. 129-134

Session 7

• 
  Michael Codish, Vitaly Lagoon: Type Dependencies for Logic Programs Using ACI-Unification. 136-145
• 
  Thorsten Altenkirch, Martin Hofmann, Thomas Streicher: Reduction-Free Normalisation for a Polymorphic System. 146
• 
  Cees Witteveen, Wiebe van der Hoek: Updating Nonmonotonic Databases. 147-153

Session 8

• 
  Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: On the Parallel Computation of Boolean Functions on Unrelated inputs. 155-161
• 
  Richard Zippel: On Satisfiability. 162-169
• 
  Yishay Mansour, Michal Parnas: On Learning Conjunctions with Malicious Noise. 170-175
• 
  Moni Naor, Sitvanit Ruah: On the Decisional Complexity of Problems Over the Reals. 176-187

Session 9 - Invited Talk

• 
  William R. Pulleyblank: The Airline Crew Pairing Optimization Problem. 189

Session 10

• 
  Benny Chor, Yuval Ishai: On Privacy and Partition Arguments. 191-194
• 
  Haim Kaplan, Ron Shamir: Physical Maps and Interval Sandwich Problems: Bounded Degrees Help. 195-201
• 
  Roded Sharan, Avi Wigderson: A New NCAlgorithm for Perfect Matching in Bipartite Cubic Graphs. 202-207
• 
  Uriel Feige, Yuri Rabinovich: Deterministic Approximation of the Cover Time. 208-218
• 
  Israel A. Wagner, Michael Lindenbaum, Alfred M. Bruckstein: Smell as a Computational Resource - A Lesson We Can Learn from the Ant. 219-230