Catálogo de publicaciones - libros

We present lower bounds on the space required to estimate the quantiles of a stream of numerical values. Quantile estimation is perhaps the most studied problem in the data stream model and it is relatively well understood in the basic single-pass data stream model in which the values are ordered adversarially. Natural extensions of this basic model include the in which the values are ordered randomly (e.g. [21,5,13,11,12]) and the in which an algorithm is permitted a limited number of passes over the stream (e.g. [6,7,1,19,2,6,7,19,2]). We present lower bounds that complement existing upper bounds [21,11] in both models. One consequence is an exponential separation between the random-order and adversarial-order models: using space, exact selection requires (log) passes in the adversarial-order model while (loglog) passes are sufficient in the random-order model.

We present a streaming algorithm for constructing sparse spanners and show that our algorithm out-performs significantly the state-of-the-art algorithm for this task [20]. Specifically, the of our algorithm is drastically smaller than that of the algorithm of [20], and all other efficiency parameters of our algorithm are no greater (and some of them are strictly smaller) than the respective parameters for the state-of-the-art algorithm.

We also devise a fully dynamic centralized algorithm maintaining sparse spanners. This algorithm has a very small incremental update time, and a non-trivial decremental update time. To our knowledge, this is the first fully dynamic centralized algorithm for maintaining sparse spanners that provides non-trivial bounds on both incremental and decremental update time for a wide range of stretch parameter .

We revisit the problem of memory checking considered by Blum et al. [3]. In this model, a checker monitors the behavior of a data structure residing in unreliable memory given an arbitrary sequence of user defined operations. The checker is permitted a small amount of separate reliable memory and must fail a data structure if it is not behaving as specified and pass it otherwise. How much additional reliable memory is required by the checker? First, we present a checker for an implementation of a priority queue. The checker uses space where is the number of operations performed. We then present a using only (log log) space, that, with probability at least 1 − , will fail the priority queue if it is -far (defined appropriately) from operating like a priority queue and pass the priority queue if it operates correctly. Finally, we then prove a range of lower bounds that complement our checkers.

The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that the trace equivalence remains undecidable even if the number of labels is restricted to two. The undecidability result holds also for the simulation of two-label BPP processes. These results imply undecidability of some behavioral type systems for the -calculus.

This paper provides new insight into the connection between the trace-based lower part of van Glabbeek’s linear-time, branching-time spectrum and its simulation-based upper part. We establish that ready simulation is fully abstract with respect to failures inclusion, when adding the conjunction operator that was proposed by the authors in [TCS 373(1–2):19–40] to the standard setting of labelled transition systems with (CSP-style) parallel composition. More precisely, we actually prove a stronger result by considering a coarser relation than failures inclusion, namely a preorder that relates processes with respect to inconsistencies that may arise under conjunctive composition. Ready simulation is also shown to satisfy standard logic properties and thus commends itself for studying mixed operational and logic languages.

We propose axiomatizing some stochastic games, in a continuous state space setting, using continuous belief functions, resp. plausibilities, instead of measures. Then, stochastic games are just variations on continuous Markov chains. We argue that drawing at random along a belief function is the same as letting the probabilistic player P play first, then letting the non-deterministic player C play demonically. The same holds for an angelic C, using plausibilities instead. We then define a simple modal logic, and characterize simulation in terms of formulae of this logic. Finally, we show that (discounted) payoffs are defined and unique, where in the demonic case, P maximizes payoff, while C minimizes it.

In this paper we study the chromatic number () of the binomial random graph , where  = () ≤ , for every fixed > 0. We prove that a.a.s. () is ℓ, ℓ + 1, or ℓ + 2, where ℓ is the maximum integer satisfying 2(ℓ − 1)log(ℓ − 1) ≤ .

We deal with two very related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we present a novel concept of regularity that takes into account the graph’s degree distribution, and show that if  = (,) satisfies a certain boundedness condition, then admits a regular partition. In addition, building on the work of Alon and Naor [4], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph  in polynomial time.

The cover polynomial introduced by Chung and Graham is a two-variate graph polynomial for directed graphs. It counts the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, it is an interpolation between determinant and permanent, and it is believed to be a directed analogue of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is -hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomial: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial is -hard under polynomial-time Turing reductions, while only three points are easy. Our construction uses a gadget which is easier to analyze and more general than the XOR-gadget used by Valiant in his proof that the permanent is -complete.

This paper studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables 〈ℝ, ℤ, + , < 〉 can all be recognized by weak deterministic Büchi automata, regardless of the encoding base  > 1. In this paper, we prove the reciprocal property, i.e., that a subset of ℝ that is recognizable by weak deterministic automata in every base  > 1 is necessarily definable in 〈ℝ, ℤ, + , < 〉. This result generalizes to real numbers the well-known Cobham’s theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.