Communication Complexity and Lower Bounds on Multilective
 Computations

Juraj Hromkovič

Displaying similar documents to “Communication Complexity and Lower Bounds on Multilective Computations”

On Distributive Fixed-Point Expressions

Helmut Seidl, Damian Niwiński (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For every fixed-point expression of alternation-depth , we construct a new fixed-point expression of alternation-depth 2 and size $𝒪 (r \cdot | e |)$ . Expression is equivalent to whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.

An Upper Bound on the Space Complexity of Random Formulae in Resolution

Michele Zito (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in -CNF on variables and clauses is $O (n \cdot Δ^{- \frac{1}{k - 2}})$ .

State complexity of cyclic shift

Galina Jirásková, Alexander Okhotin (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

The cyclic shift of a language , defined as SHIFT() = {}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [ (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which...

Finding the principal points of a random variable

Emilio Carrizosa, E. Conde, A. Castaño, D. Romero–Morales (2010)

RAIRO - Operations Research

Similarity:

The -principal points of a random variable with finite second moment are those points in $ℝ$ minimizing the expected squared distance from to the closest point. Although the determination of principal points involves in general the resolution of a multiextremal optimization problem, existing procedures in the literature provide just a local optimum. In this paper we show that standard Global Optimization techniques can be applied.

Lower semicontinuity of multiple µ-quasiconvex integrals

Ilaria Fragalà (2010)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

Lower semicontinuity results are obtained for multiple integrals of the kind $\int_{ℝ^{n}} f (x, \nabla_{μ} u) d μ$ , where is a given positive measure on $ℝ^{n}$ , and the vector-valued function belongs to the Sobolev space $H_{μ}^{1, p} (ℝ^{n}, ℝ^{m})$ associated with . The proofs are essentially based on blow-up techniques, and a significant role is played therein by the concepts of tangent space and of tangent measures to . More precisely, for fully general , a notion of quasiconvexity for along the tangent bundle to , turns out to be necessary for...