Performance of multi-variable flipping SAT procedures

[Subbarao Kambhampati <rao@parichaalak.eas.asu.edu>]

Someone asked in the last class about whether GSAT variants that flip
multiple variables simultaneously per iteration (i.e., explore
k-neighborhoods) were tried.  I said that they probably were tried and 
found not to be competitive. 

Here is a recent paper that does an interesting analysis of multi-flip
GSAT solvers and seems to suggest that multi-flip version can infact
do well overall.

http://www.cs.uwm.edu/~mali/conferences/mfsat-ictai.pdf

rao