On the operations over relations in the relational model data with two types of null values.
On the Optimality of Sample-Based Estimates of the Expectation of the Empirical Minimizer***
We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the empirical minimizer in a data dependent manner. We establish three main results. First, we provide an algorithm that upper bounds the expectation of the empirical minimizer in a completely data-dependent manner. This bound is based on a structural result due to Bartlett and Mendelson, which relates...
On the oriented game chromatic number.
On the orthogonalization of arbitrary Boolean formulae.
On the parallel complexity of linear groups
On the parallel complexity of the alternating hamiltonian cycle problem
On the parallel complexity of the alternating Hamiltonian cycle problem
Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...
On the parameterized complexity of approximate counting
In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class , the parameterized analogue of . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.
On the parameterized complexity of approximate counting
In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class , the parameterized analogue of . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.
On the performance and stability of a sample gated conflict resolution algorithm
On the periodicity of morphisms on free monoids
On the permutations generated by Sturmian words.
On the positive and the inversion complexity of Boolean functions
On the power of parallel communicating grammar systems with right-linear components
On the power of randomization for job shop scheduling with -units length tasks
In the job shop scheduling problem -units-, there are machines and each machine has an integer processing time of at most time units. Each job consists of a permutation of tasks corresponding to all machines and thus all jobs have an identical dilation . The contribution of this paper are the following results; (i) for jobs and every fixed , the makespan of an optimal schedule is at most , which extends the result of [3] for ; (ii) a randomized on-line approximation algorithm for -units-...
On the power of randomization for job shop scheduling with k-units length tasks
In the job shop scheduling problem k-units-Jm, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results; (i) for jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3] for k=1; (ii) a randomized on-line approximation...
On the product of all elements in a finite group.
On the product of balanced sequences
The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems...
On the product of balanced sequences
The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems...
On the proper intervalization of colored caterpillar trees
This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For...