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-022 | 11th April 2003
Piotr Berman, Marek Karpinski, Alexander D. Scott

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

We study approximation hardness and satisfiability of bounded
occurrence uniform instances of SAT. Among other things, we prove
the inapproximability for SAT instances in which every clause has
exactly 3 literals and each variable occurs exactly 4 times,
and display an explicit ... more >>>


TR03-021 | 4th April 2003
Mikhail Vyalyi

QMA=PP implies that PP contains PH

We consider possible equality QMA=PP and give an argument
against it. Namely, this equality implies that PP contains PH. The argument is based on the strong form of Toda's theorem and
the strengthening of the proof for inclusion $QMA\subseteq PP$ due to Kitaev and Watrous.

more >>>

TR03-020 | 27th March 2003
Elad Hazan, Shmuel Safra, Oded Schwartz

On the Hardness of Approximating k-Dimensional Matching

We study bounded degree graph problems, mainly the problem of
k-Dimensional Matching \emph{(k-DM)}, namely, the problem of
finding a maximal matching in a k-partite k-uniform balanced
hyper-graph. We prove that k-DM cannot be efficiently approximated
to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.
This ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint