**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...

**IP = PSPACE**

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