Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 39 Issue 4, Oct. 1992

An optimal on-line algorithm for metrical task system
Allan Borodin, Nathan Linial, Michael E. Saks
Pages: 745-763
DOI: 10.1145/146585.146588
In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general on-line decision...

Nonoblivious hashing
Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel
Pages: 764-782
DOI: 10.1145/146585.146591
Nonoblivious hashing, where information gathered from unsuccessful probes is used to modify subsequent probe strategy, is introduced and used to obtain the following results for static lookup on full tables: (1) An...

The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels
Yishay Mansour, Baruch Schieber
Pages: 783-799
DOI: 10.1145/146585.146596
The efficiency of data-link protocols for reliable transmission of a sequence of messages over non-FIFO physical channels is discussed. The transmission has to be on-line; i.e., a message cannot be accessed by the transmitting station before the...

Finite state verifiers I: the power of interaction
Cynthia Dwork, Larry Stockmeyer
Pages: 800-828
DOI: 10.1145/146585.146599
An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: (1) IPSs in which the verifier uses private...

Finite state verifiers II: zero knowledge
Cynthia Dwork, Larry Stockmeyer
Pages: 829-858
DOI: 10.1145/146585.146601
The zero knowledge properties of interactive proof systems (IPSs) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: (1) There is a language...

Algebraic methods for interactive proof systems
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
Pages: 859-868
DOI: 10.1145/146585.146605
A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role...

Adi Shamir
Pages: 869-877
DOI: 10.1145/146585.146609
In this paper, it is proven that when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space.

IP = SPACE: simplified proof
A. Shen
Pages: 878-880
DOI: 10.1145/146585.146613
Lund et al. [1] have proved that PH is contained in IP. Shamir [2] improved this technique and proved that PSPACE = IP. In this note, a slightly simplified version of Shamir's proof is presented, using degree reductions instead of simple...

On the correctness of orphan management algorithms
Maurice Herlihy, Nancy Lynch, Michael Merritt, William Weihl
Pages: 881-930
DOI: 10.1145/146585.146616
In a distributed system, node failures, network delays, and other unpredictable occurences can result in orphan computations—subcomputations that continue to run but whose results are no longer needed. Several algorithms...

A VLSI decomposition of the deBruijn graph
Oliver Collins, Sam Dolinar, Robert McEliece, Fabrizio Pollara
Pages: 931-948
DOI: 10.1145/146585.146620
The deBruijn graph Bn is the state diagram for an n-stage binary shift register. It has 2n vertices and 2n + 1...

Efficient dataflow analysis of logic programs
Saumya K. Debray
Pages: 949-984
DOI: 10.1145/146585.146624
A framework for efficient dataflow analyses of logic programs is investigated. A number of problems arise in this context: aliasing effects can make analysis computationally expensive for sequential logic programming languages; synchronization...

Corrigenda: M. B. Dillencourt, H. Samet, and M. Tamminen,
M. B. Dillencourt, H. Samet, M. Tamminen
Page: 985
DOI: 10.1145/146585.1189955