This paper continues the investigation of the connection between proof
systems and approximation. The emphasis is on proving ``tight''
non-approximability results via consideration of measures like the
``free bit complexity'' and the ``amortized free bit complexity'' of
proof systems.

The first part of the paper presents a collection of new ... more >>>

We study dense instances of several covering problems. An instance of
the set cover problem with $m$ sets is dense if there is $\epsilon>0$
such that any element belongs to at least $\epsilon m$ sets. We show
that the dense set cover problem can be approximated with ... more >>>

We prove that Minimum vertex cover on 4-regular hyper-graphs (or
in other words, hitting set where all sets have size exactly 4),
is hard to approximate within 2 - \epsilon.
We also prove that the maximization version, in which we
are allowed to pick ... more >>>

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

We show Minimum Vertex Cover NP-hard to approximate to within a factor
of 1.3606. This improves on the previously known factor of 7/6.

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

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$
(instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even,
and by Monien and Speckenmeyer in 1985. The improvement of the vanishing
factor comes as an application of the recent results of Arora, Rao, and Vazirani
that improved ... more >>>

We consider the problem of estimating the size, $VC(G)$, of a
minimum vertex cover of a graph $G$, in sublinear time,
by querying the incidence relation of the graph. We say that
an algorithm is an $(\alpha,\eps)$-approximation algorithm
if it outputs with high probability an estimate $\widehat{VC}$
such that ... more >>>

Many approximation algorithms have been presented in the last decades
for hard search problems. The focus of this paper is on cryptographic
applications, where it is desired to design algorithms which do not
leak unnecessary information. Specifically, we are interested in
private approximation algorithms -- efficient algorithms ... more >>>

We study semidefinite programming relaxations of Vertex Cover arising from
repeated applications of the LS+ ``lift-and-project'' method of Lovasz and
Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality
gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>

We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector
chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to
$O(1/ \epsilon)$ tightenings we show ... more >>>

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

A symmetric representation for a set of objects requires the same amount of space for the set as for its complement. Complexity classifications that are based on the length of the input can depend on whether the representation is symmetric. In this article we describe a symmetric representation scheme for ... more >>>

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that ... more >>>

Computing kernels for the hitting set problem (the problem of
finding a size-$k$ set that intersects each hyperedge of a
hypergraph) is a well-studied computational problem. For hypergraphs
with $m$ hyperedges, each of size at most~$d$, the best algorithms
can compute kernels of size $O(k^d)$ in ... more >>>