2. ISTCS 1993: Natanya, Israel

Invited Talk 1

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

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Invited Talk 2

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

Session 5

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

Session 6

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

Invited Talk 3

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

Session 7

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

Session 8

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

Session 9

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

Session 10

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