Oded Goldreich

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

Oded Goldreich, Dana Ron

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

Oded Goldreich

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