Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Complexity of Approximation:
TR01-102 | 18th December 2001
Oded Goldreich

Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that

(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size ... more >>>

TR04-013 | 10th February 2004
Oded Goldreich, Dana Ron

On Estimating the Average Degree of a Graph.

Following Feige, we consider the problem of
estimating the average degree of a graph.
Using ``neighbor queries'' as well as ``degree queries'',
we show that the average degree can be approximated
arbitrarily well in sublinear time, unless the graph is extremely sparse
(e.g., unless the graph has a sublinear ... more >>>

TR05-018 | 6th February 2005
Oded Goldreich

On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

ISSN 1433-8092 | Imprint