Minimal distance of propositional models

DOI10.1007/s00224-018-9896-8zbMath1430.68120arXiv1502.06761OpenAlexW2114994281WikidataQ128729043 ScholiaQ128729043MaRDI QIDQ2322705

Gernot Salzer, Mike Behrisch, Miki Hermann, Stefan Mengel

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.06761

zbMATH Keywords

optimization problemsHamming distanceconstraint satisfaction problemapproximation.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Cites Work

• Some computational aspects of DISTANCE SAT
• Structure identification of Boolean relations and plain bases for co-clones
• Bases for Boolean co-clones
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On the Hamming distance of constraint satisfaction problems.
• Weak bases of Boolean co-clones
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• As Close as It Gets
• Give Me Another One!
• The algebras of partial functions and their invariants
• Closure properties of constraints
• The intractability of computing the minimum distance of a code
• Hardness of approximating the minimum distance of a linear code
• Function Algebras on Finite Sets
• The complexity of satisfiability problems
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Partial Polymorphisms and Constraint Satisfaction Problems
• A Theorem on Boolean Matrices
• The Next Whisky Bar
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal distance of propositional models