Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 54 Issue 6, December 2007

On counting homomorphisms to directed acyclic graphs
Martin Dyer, Leslie Ann Goldberg, Mike Paterson
Article No.: 27
DOI: 10.1145/1314690.1314691

It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes that lie strictly between them. Thus, if P ≠ NP, it is not possible to classify NP using any finite collection of complexity classes....

Equivalence between priority queues and sorting
Mikkel Thorup
Article No.: 28
DOI: 10.1145/1314690.1314692

We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to n keys in S(n) time per key, then there is a priority queue supporting delete and insert in...

A testing scenario for probabilistic processes
Ling Cheung, Mariëlle Stoelinga, Frits Vaandrager
Article No.: 29
DOI: 10.1145/1314690.1314693

We introduce a notion of finite testing, based on statistical hypothesis tests, via a variant of the well-known trace machine. Under this scenario, two processes are deemed observationally equivalent if they cannot be distinguished by any finite...

Time lower bounds for implementations of multi-writer snapshots
Faith Ellen, Panagiota Fatourou, Eric Ruppert
Article No.: 30
DOI: 10.1145/1314690.1314694

A snapshot object is an abstraction of the problem of obtaining a consistent view of the contents of shared memory in a distributed system, despite concurrent changes to the memory. There are implementations of m-component snapshot objects...

On specification of Read/Write shared variables
Sibsankar Haldar, K. Vidyasankar
Article No.: 31
DOI: 10.1145/1314690.1314695

A shared variable is an abstraction of persistent interprocess communication. Processors execute operations, often concurrently, on shared variables to exchange information among themselves. The behavior of operation executions is required to be...

Priority sampling for estimation of arbitrary subset sums
Nick Duffield, Carsten Lund, Mikkel Thorup
Article No.: 32
DOI: 10.1145/1314690.1314696

From a high-volume stream of weighted items, we want to create a generic sample of a certain limited size that we can later use to estimate the total weight of arbitrary subsets. Applied to Internet traffic analysis, the items could be records...