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

TR05-013 | 22nd December 2004
Bin Fu

Theory and Application of Width Bounded Geometric Separator

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


TR05-012 | 17th January 2005
Luca Trevisan, Salil Vadhan, David Zuckerman

Compression of Samplable Sources

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


TR05-011 | 21st December 2004
Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

Autoreducibility, Mitoticity, and Immunity

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


previous PreviousNext next


ISSN 1433-8092 | Imprint