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"
}

Paper.

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.