A RANDOM BIT-FLIPPING METHOD FOR SEEKING AGREEMENT

Recently Papadimitriou has proposed a randomized ''bit-flipping'' meth od for solving the 2-satisfiability problem, and the author has propos ed a randomized recoloring method which, given a 3-colorable graph, fi nds a 2-coloring of the vertices so that no triangle is monochromatic. Both methods involve finding a ''bad'' configuration (unsatisfied cla use, monochromatic triangle) and randomly changing one of the bits inv olved. In this paper we see how these problems and methods fit natural ly in a more general geometrical context in which we seek a vector whi ch ''agrees'' with a given collection of vectors; and we propose a sim ple ''bit-flipping'' method for the more general problem, which extend s the solution methods for the two problems mentioned above. Further, we consider deterministic methods to handle such problems, and in part icular we see how to solve the above ''triangle problem'' for 3-colora ble graphs deterministically in polynomial time. (C) 1996 John Wiley & Sons, Inc.