Minimal distance of propositional models
From MaRDI portal
Publication:2322705
DOI10.1007/s00224-018-9896-8zbMath1430.68120arXiv1502.06761MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
03B05: Classical propositional logic
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R07: Computational aspects of satisfiability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
