3. ISTCS 1995: Tel Aviv, Israel

Third Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings. IEEE Computer Society, 1995, ISBN 0-8186-6915-2

Invited Talk

G. Gemünd, M. Jakob, Werner Massonne, Wolfgang J. Paul, B. Spengler: High Performance Transaction Systems on the SB-PRAM. 1-10 BibTeX

Session 1

Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann: Improved Optimal Shared Memory Simulations, and the Power of Reconfiguration. 11-19 BibTeX
Ishai Ben-Aroya, Ilan Newman, Assaf Schuster: Randomized Single-Target Hot-Potato Routing. 20-29 BibTeX
Uriel Feige: Observations on Hot Potato Routing. 30-39 BibTeX

Session 2

Nikolai K. Vereshchagin: NP-sets are Co-NP-immune Relative to a Random Oracle. 40-45 BibTeX
Nikolai K. Vereshchagin: Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. 46-51 BibTeX
Gábor Tardos, David A. Mix Barrington: A Lower Bound on the Mod 6 Degree of the OR Function. 52-56 BibTeX

Session 3

Peter Høyer: A General Technique for Implementation of Efficient Priority Queues. 57-66 BibTeX
Jeanette P. Schmidt: All Shortest Paths in Weighted Grid Graphs and its Application to Finding All Approximate Repeats in Strings. 67-77 BibTeX

Session 4

Matthew J. Katz: Improved Algorithms in Geometric Optimization via Expanders. 78-87 BibTeX
Dorit Dor, Uri Zwick: Finding percentile elements. 88-97 BibTeX

Session 5

Hagit Brit, Shlomo Moran, Gadi Taubenfeld: Public Data Structures: Counters as a Special Case (Abridged Version). 98-110 BibTeX
Amir Ben-Dor, Amos Israeli, Asaf Shirazi: Dynamic Counting. 111-120 BibTeX
Yaron Riany, Nir Shavit, Dan Touitou: Towards A Practical Snapshot Algorithm. 121-129 BibTeX

Session 6

Rob Gerth, Ruurd Kuiper, Doron Peled, Wojciech Penczek: A Partial Order Approach to Branching Time Logic Model Checking. 130-139 BibTeX
David Harel, Eli Singerman: More on Nonregular PDL: Expressive Power, Finite Models, Fibonacci Programs. 140-149 BibTeX
H. Petersen: Automata with Sensing Heads. 150-157 BibTeX

Invited Paper

Pavel A. Pevzner, Michael S. Waterman: Open Combinatorial Problems in Computational Molecular Biology. 158-173 BibTeX

Session 7

Carsten Rössner, Claus-Peter Schnorr: Computation of Highly Regular Nearby Points. 174-181 BibTeX
Uriel Feige, Michel X. Goemans: Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. 182-189 BibTeX

Session 8

Katalin Friedl, Madhu Sudan: Some Improvements to Total Degree Tests. 190-198 BibTeX
Mihir Bellare, Uriel Feige, Joe Kilian: On the Role of Shared Randomness in Two Prover Proof Systems. 199-208 BibTeX
Joe Kilian, Moni Naor: On the Complexity of Statistical Reasoning (extended abtract). 209-217 BibTeX

Invited Talk

Avi Wigderson: Computational Pseudo-Randomness. 218-219 BibTeX

Session 9

Tal Goldberg, Uri Zwick: Optimal deterministic approximate parallel prefix sums and their applications. 220-228 BibTeX
Omer Berkman, Phillip B. Gibbons, Yossi Matias: On the Power of Randomization for the Common PRAM. 229-240 BibTeX
Jiri Sgall: Randomized On-Line Scheduling of Parallel Jobs. 241-250 BibTeX

Session 10

Shlomo Moran: Using Approximate Agreement to Obtain Complete Disagreement: The Output Structure of Input-Free Asynchronous Computations. 251-257 BibTeX
Jon M. Kleinberg, Hagit Attiya, Nancy A. Lynch: Trade-offs between Message Delivery and Quiesce Times in Conection Management Protocols (Preliminary Report). 258-267 BibTeX
Alain J. Mayer, Moni Naor, Larry J. Stockmeyer: Local Computations on Static and Dynamic Graphs (Preliminary Version). 268-278 BibTeX