We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of $\sqrt{n}$, of optimization problems in integer lattices; specifically, the closest vector problem (CVP), and the shortest vector problem (SVP). These interactive proofs are for the ``coNP direction''; that is, we give an interactive ... more >>>

We show that computing the approximate length of the shortest vector in a lattice within a factor c is NP-hard for randomized reductions for any constant cmore >>>

We prove hardness results for approximating set splitting problems and also instances of satisfiability problems which have no ``mixed'' clauses, i.e all clauses have either all their literals unnegated or all of them negated. Recent results of Hastad imply tight hardness results for set splitting when all sets have size ... 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 B = pn elements in an ... more >>>

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

In the {\sc $k$-center} problem, the input is a bound $k$ and $n$ points with the distance between every two of them, such that the distances obey the triangle inequality. The goal is to choose a set of $k$ points to serve as centers, so that the maximum distance from ... more >>>

We investigate the computational hardness of the {\sc Connectivity}, the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range Assignment Problems in $\R^2$ and $\R^3$. We present new reductions for the {\sc Connectivity} problem, which are easily adapted to suit the other two problems. All reductions are considerably simpler ... more >>>

Producing a small DNF expression consistent with given data is a classical problem in computer science that occurs in a number of forms and has numerous applications. We consider two standard variants of this problem. The first one is two-level logic minimization or finding a minimal DNF formula consistent with ... more >>>

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding learning ... more >>>

Learning an unknown halfspace (also called a perceptron) from labeled examples is one of the classic problems in machine learning. In the noise-free case, when a halfspace consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that ... more >>>

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>

We prove a strong inapproximability result for routing on directed graphs with low congestion. Given as input a directed graph on $N$ vertices and a set of source-destination pairs that can be connected via edge-disjoint paths, we prove that it is hard, assuming NP doesn't have $n^{O(\log\log n)}$ time randomized ... more >>>

We study the polynomial reconstruction problem for low-degree multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ... more >>>

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m pricable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization ... more >>>

In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for ... more >>>

In the undirected Edge-Disjoint Paths problem with Congestion (EDPwC), we are given an undirected graph with $V$ nodes, a set of terminal pairs and an integer $c$. The objective is to route as many terminal pairs as possible, subject to the constraint that at most $c$ demands can be routed ... more >>>

In a two player game, a referee asks two cooperating players (who are not allowed to communicate) questions sampled from some distribution and decides whether they win or not based on some predicate of the questions and their answers. The parallel repetition of the game is the game in which ... more >>>

We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error $o(1)$. The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the ... more >>>

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>