Cover Image

Small unsatisfiable $k$-CNFs with bounded literal occurrence

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zhang, Tianwei, Peitl, Tomáš, Szeider, Stefan
Format:	Preprint
Published:	2024
Subjects:	Discrete Mathematics Computational Complexity Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
by: Geniet, Colin, et al.
Published: (2026)

Rice-like complexity lower bounds for Boolean and uniform automata networks
by: Goubault-Larrecq, Aliénor, et al.
Published: (2024)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
by: Barto, Libor, et al.
Published: (2024)

The Unit Gap: How Sharing Works in Boolean Circuits
by: Krinkin, Kirill
Published: (2026)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

Restricted CSPs and F-free Digraph Algorithmics
by: Guzmán-Pro, Santiago, et al.
Published: (2025)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
by: Seppelt, Tim
Published: (2023)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
by: Kiefer, Sandra, et al.
Published: (2025)

Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
by: Callard, Antonin, et al.
Published: (2024)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
by: Dwivedi, Prateek, et al.
Published: (2026)

Better Extension Variables in DQBF via Independence
by: Chew, Leroy, et al.
Published: (2025)

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

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

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

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

Graph Homomorphisms and Universal Algebra
by: Bodirsky, Manuel
Published: (2026)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

CMSO-transducing tree-like graph decompositions
by: Campbell, Rutger, et al.
Published: (2024)

Weighted basic parallel processes and combinatorial enumeration
by: Clemente, Lorenzo
Published: (2024)

Continuous Petri Nets Faithfully Fluidify Most Permissive Boolean Networks
by: Haar, Stefan, et al.
Published: (2025)

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

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Logic-based analogical proportions
by: Antić, Christian
Published: (2024)

A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
by: Fuchser, Janne, et al.
Published: (2025)

Nested Sequents for Intuitionistic Grammar Logics via Structural Refinement
by: Lyon, Tim S.
Published: (2022)

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
by: Adler, Isolde, et al.
Published: (2025)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

From the Finite to the Infinite: Sharper Asymptotic Bounds on Norin's Conjecture via SAT
by: Kirchweger, Markus, et al.
Published: (2025)

Home Spaces and Invariants to Analyze Parameterized Petri Nets
by: Memmi, Gerard
Published: (2024)

Hypergraph rewriting and Causal structure of $λ-$calculus
by: Bajaj, Utkarsh
Published: (2024)

Learning Foundations Beneath the Stars
by: Cardone, Felice, et al.
Published: (2026)

On the Subspace Orbit Problem and the Simultaneous Skolem Problem
by: Bacik, Piotr, et al.
Published: (2026)

SAT-Solving the Poset Cover Problem
by: Yuan, Chih-Cheng Rex, et al.
Published: (2025)

Verifying Sampling Algorithms via Distributional Invariants
by: Zilken, Daniel, et al.
Published: (2025)

Efficient reversal of transductions of sparse graph classes
by: Dreier, Jan, et al.
Published: (2026)

On the number of asynchronous attractors in AND-NOT Boolean networks
by: Trinh, Van-Giang, et al.
Published: (2025)