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

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Invited Paper

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

Session 7

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

Session 8

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

Invited Talk

Avi Wigderson: Computational Pseudo-Randomness. 218-219

Session 9

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

Session 10

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

Last update Wed May 22 15:46:08 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page