In the eighties, when Steve was a sophomore at Princeton, we wrote a technical report on local search for MAX-CSP(Gamma).

@TECHREPORT{Vavasis-TR302, AUTHOR = "Karl Lieberherr and Stephen A. Vavasis", TITLE = "Limitations of Local Search: An Application of Bernstein's Proof of Weierstrass' Theorem", INSTITUTION = "Princeton University, Dept. of EECS", YEAR = 1982, NUMBER = "302", Note = "http://www.ccs.neu.edu/research/demeter/biblio/vavasis-tr302.html" }

Discussion:

This paper introduces difference polynomials differ(F,I1) which give the expected number of satisfied constraints in F among all assignments which differ deom I1 in exactly k variables. Those polynomials are used to explore the neighborhood of a given assignment I1. We use the difference polynomials as follows: Start with I1; repeat if max(differ(F,I1)) gives a better assignment I1 = better assignment; until no improvement; This maps I1 to a locally optimal assignment which satisfies the P-optimal threshold. This formulation is simpler than using an n-mapping. Alternatively, we could talk about the polynomial differ_x(F,I1) which gives the expected number of satisfied constraints in F if we n-map each literal in I1 with probability x. This is simpler because it is only a polynomial in one variable x and not k and n. In future papers we should use difference polynomials instead of mean(n,k) or mean(x). Let's define an assignment I1 to be maximal, if the difference polynomial differ_x(F,I1), after maximization, does not give a better assignment. More precise: An assignment I1 for an instance F is maximal, if MAX-DIFFER(F, I1) and DERANDOMIZED_MAX-DIFFER(F, I1) do not return a better assignment than I1. MAX-DIFFER: computes the maximum bias and uses it set the variables. DERANDOMIZED MAX-DIFFER: derandomized version of MAX-DIFFER Given a formula F, the problem of finding a maximal assignment can be solved in polynomial time. (Note: maximum != maximal; finding a maximum assignment is NP-complete) If the transition system MAX-CSP(Gamma) produces a non-maximal assignment then the next step will be UPDATE. Conjecture: MAX-CSP(Gamma) will produce only few non-maximal assignments compared to the number of maximal assignments produced. The paper makes an interesting connection between relations and continuous functions on [0,1]. Unfortunately, the technical report does not talk about how to compute P-optimal thresholds while the the conference version does.