Publication

Survey Propagation Inspired Algorithms for Satisfiability

Nicolas Macris
2008
Reports

Abstract

In this note we develop generalized Survey Propagation (SP) equations from the cavity method. We quantize the message space of the messages to develop a message passing rule. We investigate a framework of greedy algorithms for finding out satisfying assignment inspired by the new SP rule. We show that the recent Hajiaghayi-Sorkin algorithm for satisfiability is a special case in this framework of algorithms and the lower bound on the conjectured threshold given by the Hajiaghayi-Sorkin algorithm can be improved. This improvement is shown by experiments.

Official source

https://infoscience.epfl.ch/entities/publication/901647b4-df58-44fd-a286-351372076a5b

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Nicolas Macris
2008
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/901647b4-df58-44fd-a286-351372076a5b

About this result

Related concepts (25)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city.

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Related publications (20)

Survey Propagation Inspired Algorithms for Satisfiability

Chat with Graph Search

Fundamental computational limits of weak learnability in high-dimensional multi-index models

Observations on the LPN Solving Algorithm from Eurocrypt'16

New Bounds for Random Constraint Satisfaction Problems via Spatial Coupling