Cover Image

CNFs and DNFs with Exactly $k$ Solutions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chandran, L. Sunil, Gajjala, Rishikesh, Meel, Kuldeep S.
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics Data Structures and Algorithms Logic in Computer Science Combinatorics Logic
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

Color Refinement for Relational Structures
by: Scheidt, Benjamin, et al.
Published: (2024)

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
by: Zhang, Tianwei, et al.
Published: (2024)

Separability Properties of Monadically Dependent Graph Classes
by: Bonnet, Édouard, et al.
Published: (2025)

Epsilon-saturation for stable graphs and Littlestone classes
by: Malliaris, Maryanthe, et al.
Published: (2025)

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
by: Mählmann, Nikolas
Published: (2025)

Advances in Algorithmic Meta Theorems
by: Siebertz, Sebastian, et al.
Published: (2024)

Existential Positive Transductions of Sparse Graphs
by: Mählmann, Nikolas, et al.
Published: (2026)

Characterizations of monadically dependent tree-ordered weakly sparse structures
by: Buffière, Hector, et al.
Published: (2026)

Decomposition horizons and a characterization of stable hereditary classes of graphs
by: Braunfeld, Samuel, et al.
Published: (2022)

On first-order transductions of classes of graphs
by: Braunfeld, Samuel, et al.
Published: (2022)

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
by: Dreier, Jan, et al.
Published: (2024)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

North-East Lattice Paths Avoiding $k$ Collinear Points via Satisfiability
by: Barnoff, Aaron, et al.
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

First order complexity of finite random structures
by: Demin, Danila, et al.
Published: (2024)

Exact Exploration
by: Blass, Andreas, et al.
Published: (2024)

Flip-width: Cops and Robber on dense graphs
by: Toruńczyk, Szymon
Published: (2023)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2022)

The unstable formula theorem revisited via algorithms
by: Malliaris, Maryanthe, et al.
Published: (2022)

Agnostic Online Learning and Excellent Sets
by: Malliaris, Maryanthe, et al.
Published: (2021)

The domino problem is decidable for robust tilesets
by: Aubrun, Nathalie, et al.
Published: (2024)