We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.
As an ... more >>>

We introduce a new hierarchy over monotone set functions, that we refer to as $MPH$ (Maximum over Positive Hypergraphs).
Levels of the hierarchy correspond to the degree of complementarity in a given function.
The highest level of the hierarchy, $MPH$-$m$ (where $m$ is the total number of items) captures all ... more >>>

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,
the welfare maximization problem requires that every item be allocated to exactly one player,
and one wishes to maximize the sum of values obtained by the players,
as computed ... more >>>

Motivated by the study of Parallel Repetition and also by the Unique
Games Conjecture, we investigate the value of the ``Odd Cycle Games''
under parallel repetition. Using tools from discrete harmonic
analysis, we show that after $d$ rounds on the cycle of length $m$,
the value of the game is ... more >>>

Let $\phi$ be a 3CNF formula with n variables and m clauses. A
simple nonconstructive argument shows that when m is
sufficiently large compared to n, most 3CNF formulas are not
satisfiable. It is an open question whether there is an efficient
refutation algorithm that for most such formulas proves ... more >>>

We consider the problem of finding a maximum independent set in a
random graph. The random graph $G$ is modelled as follows. Every
edge is included independently with probability $\frac{d}{n}$, where
$d$ is some sufficiently large constant. Thereafter, for some
constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ... more >>>

Max-Satisfy is the problem of finding an assignment that satisfies
the maximum number of equations in a system of linear equations
over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no
polynomial time algorithm for the problem achieving an
approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number
of ... more >>>

We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently
known for the Max Cut problem on general graphs~\cite{GW95}.
We consider a semidefinite relaxation of the Max Cut problem,
round it using the ... more >>>