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$. more >>>

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 random ... more >>>