On the enumeration of signatures of XOR-CNF's

February 28, 2024 Β· Declared Dead Β· πŸ› Workshop on Algorithms and Data Structures

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Nadia Creignou, Oscar Defrain, FrΓ©dΓ©ric Olive, Simon Vilmin arXiv ID 2402.18537 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM, math.CO Citations 1 Venue Workshop on Algorithms and Data Structures Last Checked 4 months ago
Abstract
Given a CNF formula $\varphi$ with clauses $C_1, \dots, C_m$ over a set of variables $V$, a truth assignment $\mathbf{a} : V \to \{0, 1\}$ generates a binary sequence $Οƒ_\varphi(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a}))$, called a signature of $\varphi$, where $C_i(\mathbf{a})=1$ if clause $C_i$ evaluates to 1 under assignment $\mathbf{a}$, and $C_i(\mathbf{a})=0$ otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, BΓ©rczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted