Laboratoire d'informatique de l'École polytechnique

The laboratory LIX

The abbreviation LIX stands for Laboratoire d'Informatique de l'Ecole polytechnique (Computer Science Laboratory of the École polytechnique), where the letter X represents the Polytechnique per French tradition. LIX is a mixed research unit (UMR 7161) consisting of two tutelles: the École polytechnique and the National Center for Scientific Research (CNRS). LIX falls under the jurisdiction of the INS2I division (which stands for the National Institute of Sciences of Information and their Interactions) of CNRS.

Sémin'Ouvert : « Minimal Distance of Propositional Models » par Miki Hermann (équipe AlCo)

We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula (Next Solution) or that does not need to satisfy it (Nearest Solution). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments (Min Solution Distance).

For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, polyAPX, or equivalence to well-known hard optimization problems.

This is joint work with Mike Behrisch (TU Wien), Stefan Mengel (CRIL), et Gernot Salzer (TU Wien).