The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject.
We consider the approximation ability of randomized search for the class of ... more >>>

We show a construction of a PCP with both sub-constant error and
almost-linear size. Specifically, for some constant alpha in (0,1),
we construct a PCP verifier for checking satisfiability of
Boolean formulas that on input of size n uses log n + O((log
n)^{1-alpha}) random bits to query a constant ... more >>>

We present algebraic conditions on constraint languages \Gamma
that ensure the hardness of the constraint satisfaction problem
CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL.
These criteria also give non-expressibility results for various
restrictions of Datalog. Furthermore, we show that if
CSP(\Gamma) is not first-order definable then it ... more >>>