Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR02-030 | 3rd June 2002
Lars Engebretsen, Jonas Holmerin, Alexander Russell

Inapproximability Results for Equations over Finite Groups

Revisions: 1

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 >>>


TR02-029 | 3rd June 2002
Marek Karpinski, Yakov Nekrich

Parallel Construction of Minimum Redundancy Length-Limited Codes

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 >>>


TR02-028 | 15th May 2002
Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

Power from Random Strings

Revisions: 1 , Comments: 1

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 >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint