Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem

We formalize the class of “sequential local algorithms" and show that these algorithms fail to find satisfying assignments on random instances of the “Not-All-Equal-$K$-SAT” (NAE-$K$-SAT) problem if the number of message passing iterations is bounded by a function moderately growing in the numb...

Full description

Bibliographic Details
Main Authors: Gamarnik, David, Sudan, Madhu
Other Authors: Sloan School of Management
Format: Article
Language:en_US
Published: Society for Industrial and Applied Mathematics 2017
Online Access:http://hdl.handle.net/1721.1/110193
https://orcid.org/0000-0001-8898-8778