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

TR02-027 | 30th April 2002
Irit Dinur, Venkatesan Guruswami, Subhash Khot

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that ``hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>


TR02-026 | 7th April 2002
Boaz Barak, Yehuda Lindell

Strict Polynomial-time in Simulation and Extraction

Revisions: 2

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>


TR02-025 | 26th April 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

We give polynomial time approximation schemes for the problem
of partitioning an input set of n points into a fixed number
k of clusters so as to minimize the sum over all clusters of
the total pairwise distances in a cluster. Our algorithms work
for arbitrary metric spaces as well ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint