enter search term and/or author name
On counting homomorphisms to directed acyclic graphs
Martin Dyer, Leslie Ann Goldberg, Mike Paterson
Article No.: 27
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....
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...
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
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...
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
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...