enter search term and/or author name
Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n2 barrier
Camil Demetrescu, Giuseppe F. Italiano
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
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
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
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...
An information-theoretic approach to normal forms for relational and XML data
Marcelo Arenas, Leonid Libkin
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
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...