Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 52 Issue 2, March 2005

Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n2 barrier
Camil Demetrescu, Giuseppe F. Italiano
Pages: 147-156
DOI: 10.1145/1059513.1059514
We present an algorithm for directed acyclic graphs that breaks through the O(n2) barrier on the single-operation complexity of fully dynamic transitive closure, where n is the number of edges in the graph. We can...

Lower bounds for linear degeneracy testing
Nir Ailon, Bernard Chazelle
Pages: 157-171
DOI: 10.1145/1059513.1059515
In the late nineties, Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given n numbers, do any r of them add up to 0? His lower bound of...

Simple extractors for all min-entropies and a new pseudorandom generator
Ronen Shaltiel, Christopher Umans
Pages: 172-216
DOI: 10.1145/1059513.1059516
A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure...

Trade-offs in probabilistic packet marking for IP traceback
Micah Adler
Pages: 217-244
DOI: 10.1145/1059513.1059517
There has been considerable recent interest in probabilistic packet marking schemes for the problem of tracing a sequence of network packets back to an anonymous source. An important consideration for such schemes is the number of packet header bits...

Tova Milo, Victor Vianu
Pages: 245-245
DOI: 10.1145/1059513.1059518

An information-theoretic approach to normal forms for relational and XML data
Marcelo Arenas, Leonid Libkin
Pages: 246-283
DOI: 10.1145/1059513.1059519
Normalization as a way of producing good relational database designs is a well-understood topic. However, the same problem of distinguishing well-designed databases from poorly designed ones arises in other data models, in particular, XML. While, in...

The complexity of XPath query evaluation and XML typing
Georg Gottlob, Christoph Koch, Reinhard Pichler, Luc Segoufin
Pages: 284-335
DOI: 10.1145/1059513.1059520
We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTIME in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into...