
PreviousNext
We introduce the notion of width bounded geometric separator,
develop the techniques for its existence as well as algorithm, and
apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the
disk covering problem, which seeks to determine the minimal number
of fixed size disks to cover $n$ points on ...
more >>>
We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).
1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).
Our next ... more >>>
We show the following results regarding complete sets:
NP-complete sets and PSPACE-complete sets are many-one
autoreducible.
Complete sets of any level of PH, MODPH, or
the Boolean hierarchy over NP are many-one autoreducible.
EXP-complete sets are many-one mitotic.
NEXP-complete sets are weakly many-one mitotic.
PSPACE-complete sets are weakly Turing-mitotic.
... more >>>
PreviousNext