
PreviousNext
An equation over a finite group G is an expression of form
w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted
variable, or a constant from G; such an equation is satisfiable
if there is a setting of the variables to values in G ...
more >>>
This paper presents new results on parallel constructions of the
length-limited prefix-free codes with the minimum redundancy.
We describe an algorithm for the construction of length-limited codes
that works in $O(L)$ time with $n$ processors for $L$ the
maximal codeword length.
We also describe an algorithm for a construction ...
more >>>
We consider sets of strings with high Kolmogorov complexity, mainly
in resource-bounded settings but also in the traditional
recursion-theoretic sense. We present efficient reductions, showing
that these sets are hard and complete for various complexity classes.
In particular, in addition to the usual Kolmogorov complexity measure
K, ...
more >>>
PreviousNext