Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

Pratik Worah

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>