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

TR03-040 | 3rd June 2003
Philippe Moser

RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

We use recent results on the hardness of resource-bounded
Kolmogorov random strings, to prove that RP is small in SUBEXP
else ZPP=PSPACE and NP=EXP.
We also prove that if NP is not small in SUBEXP, then
NP=AM, improving a former result which held for the measure ... more >>>


TR03-039 | 19th May 2003
Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

Theory Revision with Queries: Horn, Read-once, and Parity Formulas

A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
correctly.
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is ... more >>>


TR03-038 | 15th May 2003
Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

Asymmetric k-center is log^*n-hard to Approximate

We show that the asymmetric $k$-center problem is
$\Omega(\log^* n)$-hard to approximate unless
${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$.
Since an $O(\log^* n)$-approximation algorithm is known
for this problem, this essentially resolves the approximability
of this problem. This is the first natural problem
whose approximability threshold does not polynomially ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint