A random bit-flipping method for seeking agreement

✍ Scribed by Colin McDiarmid

• Book ID: 102656815
• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 552 KB
• Volume: 8
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199603)8:2<121::aid-rsa3>3.0.co;2-#

✦ Synopsis

Recently Papadimitriou has proposed a randomized "bit-flipping'' method for solving the 2-satisfiability problem, and the author has proposed a randomized recoloring method which, given a 3-colorable graph, finds a 2-coloring of the vertices so that no triangle is monochromatic. Both methods involve finding a "bad" configuration (unsatisfied clause, monochromatic triangle) and randomly changing one of the bits involved. In this paper we see how these problems and methods fit naturally in a more general geometrical context in which we seek a vector which "agrees" with a given collection of vectors; and we propose a simple "bit-flipping'' method for the more general problem, which extends the solution methods for the two problems mentioned above. Further, we consider deterministic methods to handle such problems, and in particular we see how to solve the above "triangle problem" for 3-colorable graphs deterministically in polynomial time.