
PreviousNext
In this paper, we are concerned with randomized OBDDs and randomized
read-k-times branching programs. We present an example of a Boolean
function which has polynomial size randomized OBDDs with small,
one-sided error, but only non-deterministic read-once branching
programs of exponential size. Furthermore, we discuss a lower bound
technique for randomized ...
more >>>
Following Ajtai's lead, Ajtai and Dwork have recently introduced a
public-key encryption scheme which is secure under the assumption
that a certain computational problem on lattices is hard on the
worst-case. Their encryption method may cause decryption errors,
though with small probability (i.e., inversely proportional to the
more >>>
The bandwidth problem is the problem of numbering the vertices of a
given graph $G$ such that the maximum difference between the numbers
of adjacent vertices is minimal. The problem has a long history and
is known to be NP-complete Papadimitriou [Pa76]. Only few special
cases ...
more >>>
PreviousNext