Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 48 Issue 3, May 2001

Unconditional security in quantum cryptography
Dominic Mayers
Pages: 351-406
DOI: 10.1145/382780.382781
Basic techniques to prove the unconditional security of quantum crypto graphy are described. They are applied to a quantum key distribution protocol proposed by Bennett and Brassard [1984]. The proof considers a practical variation on the...

An analysis of the Burrows—Wheeler transform
Giovanni Manzini
Pages: 407-430
DOI: 10.1145/382780.382782
The Burrows—Wheeler Transform (also known as Block-Sorting) is at the base of compression algorithms that are the state of the art in lossless data compression. In this paper, we analyze two algorithms that use this technique. The first...

The complexity of acyclic conjunctive queries
Georg Gottlob, Nicola Leone, Francesco Scarcello
Pages: 431-498
DOI: 10.1145/382780.382783

This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis[1981], this problem is solvable in polynomial time; its precise complexity, however, has not been...

Simplifying fault-tolerance: providing the abstraction of crash failures
Rida A. Bazzi, Gil Neiger
Pages: 499-554
DOI: 10.1145/382780.382784
The difficulty of designing fault-tolerant distributed algorithms incr eases with the severity of failures that an algorithm must tolerate, especially for systems with synchronous message passing. This paper considers methods that automatically...

A modal analysis of staged computation
Rowan Davies, Frank Pfenning
Pages: 555-604
DOI: 10.1145/382780.382785
We show that a type system based on the intuitionistic modal logic S4 provides an expressive framework for specifying and analyzing computation stages in the context of typed &lgr;-calculi and functional languages. We directly demonstrate the...