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

**Trade-offs for fully dynamic transitive closure on DAGs: breaking through the ***O*(*n*^{2} 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*(*n*^{2}) 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...

**Introduction**

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