We investigate the computational complexity of two classes of combinatorial optimization problems related to linear systems and study the relationship between their approximability properties. In the first class (MIN ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as ... more >>>

NP = PCP(log n, 1) and related results crucially depend upon the close connection between the probability with which a function passes a ``low degree test'' and the distance of this function to the nearest degree d polynomial. In this paper we study a test proposed by Rubinfeld and Sudan. ... more >>>

We study the computational complexity of an optimization version of the constraint satisfaction problem: given a set $F$ of constraint functions, an instance consists of a set of variables $V$ related by constraints chosen from $F$ and a natural number $k$. The problem is to decide whether there exists a ... more >>>

Given a finite set $S$ of points (i.e. the stations of a radio network) on a $d$-dimensional Euclidean space and a positive integer $1\le h \le |S|-1$, the \minrangeh{d} problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided that the transmission ... more >>>

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short). We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>