Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$
consisting of optimization problems for which efficient local-
search heuristics exist. We formulate a type-2 problem $\iter$
that characterizes $\PLS$ in style of Beame et al., and prove
a criterion for type-2 problems to be nonreducible to $\iter$.
As a corollary, ... more >>>

A CNF formula is k-satisfiable if each k clauses of it can be satisfied
simultaneously. Let \pi_k be the largest real number such that for each
k-satisfiable formula with variables x_i, there are probabilities p_i
with the following property: If each variable x_i is chosen randomly and
independently to be ... more >>>

We prove approximation hardness of short symmetric instances
of MAX-3SAT in which each literal occurs exactly twice, and
each clause is exactly of size 3. We display also an explicit
approximation lower bound for that problem. The bound two on
the number ... more >>>