Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, June 7-9, 1993, Proceedings. IEEE Computer Society, 1993, ISBN 0-8186-3630-0

Invited Talk 1

• 
  Shafi Goldwasser: Efficient Interactive Proofs and Applications to Approximation. 1-2

Session 1

• 
  Rafail Ostrovsky, Avi Wigderson: One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. 3-17
• 
  Michael Luby, Boban Velickovic, Avi Wigderson: Deterministic Approximate Counting of Depth-2 Circuits. 18-24
• 
  Shiva Chaudhuri: A Lower Bound for Linear Approximate Compaction. 25-32

Session 2

• 
  Danny Dolev, Yuval Harari, Michal Parnas: Finding the Neighborhood of a Query in a Dictionary. 33-42
• 
  Nimrod Megiddo, Moni Naor, David P. Anderson: The Minimum Reservation Rate Problem in Digital Audio/Video Systems. 43-48
• 
  Alon Efrat, Craig Gotsman: Subpixel Image Registration Using Circular Fiducials. 49-58

Session 3

• 
  Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Which Patterns are Hard to Find? 59-68
• 
  David Peleg, Gideon Schechtman, Avishai Wool: Approximating Bounded 0-1 Integer Linear Programs. 69-77
• 
  Edith Cohen: Using Selective Path-Doubling for Parallel Shortest-Path Computations. 78-87
• 
  Yefim Dinitz: Maintaining the 4-Edge-Connected Components of a Graph On-Line. 88-97

Session 4

• 
  Hava T. Siegelmann, Eduardo D. Sontag: Analog Computation Via Neural Networks. 98-107
• 
  Amir Ben-Dor, Shai Halevi: Zero-One Permanent is #P-Complete, A Simpler Proof. 108-117
• 
  Liming Cai, Jianer Chen: On Fixed-Parameter Tractability and Approximability of NP-Hard Optimization Problems. 118-126

Invited Talk 2

• 
  Adi Shamir: Practical Cryptography - Recent Trends and Results. 127

Session 5

• 
  Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. 128-133
• 
  Anne Condon, Diane Hernek: Random Walks on Colored Graphs. 134-140
• 
  Nathan Linial, David Peleg, Yuri Rabinovich, Michael E. Saks: Sphere Packing and Local Majorities in Graphs. 141-149

Session 6

• 
  Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir: The Las-Vegas Processor Identity Problem (How and When to Be Unique). 150-159
• 
  Yehuda Afek, Danny Hendler: On the Complexity of Global Computation in the Presence of Link Failures: The General Case. 160-166
• 
  Frank A. Stomp: Structured Design of Self-Stabilizing Programs. 167-176

Invited Talk 3

• 
  Thomas Lengauer: Algorithmic Research Problems in Molecular Bioinformatics. 177-192

Session 7

• 
  Ronald I. Greenberg, Jau-Der Shih: Feasible Offset an Optimal Offset for Single-Layer Channel Routing. 193-201
• 
  Ilan Newman, Assaf Schuster: Hot-Potato Worm Routing is Almost as Easy as Store-and-Forward Packet Routing. 202-211
• 
  Alon Itai, Hadas Shachnai: Adaptive Source Routing in High-Speed Networks. 212-221

Session 8

• 
  Kaisa Sere: A Formalization of Superposition Refinement. 222-230
• 
  Joost N. Kok, Peter M. W. Knijnenburg: Divergence Models for Atomized Statements and Parallel Choice. 231-239
• 
  Zurab Khasidashvili: On the Equivalence of Persistent Term Rewriting Systems and Recursive Program Schemes. 240-249

Session 9

• 
  Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. 250-260
• 
  Johan Håstad, Steven Phillips, Shmuel Safra: A Well-Characterized Approximation Problem. 261-265
• 
  Mihir Bellare: Interactive Proofs and Approximation: Reduction from Two Provers in One Round. 266-274
• 
  Erez Petrank: The Hardness of Approximation: Gap Location. 275-284

Session 10

• 
  Juan A. Garay, Inder S. Gopal, Shay Kutten, Yishay Mansour, Moti Yung: Efficient On-Line Call Control Algorithms. 285-293
• 
  Amos Fiat, Moty Ricklin: Competitive Algorithms for the Weighted Server Problem. 294-303
• 
  Ran El-Yaniv, Richard M. Karp: The Mortgage Problem. 304-312