Cover Image

Proving Unsatisfiability with Hitting Formulas

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Filmus, Yuval, Hirsch, Edward A., Riazanov, Artur, Smal, Alexander, Vinyals, Marc
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Logic 03F20 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hypersequent Calculi Have Ackermannian Complexity
by: Balasubramanian, A. R., et al.
Published: (2026)

Deducibility in the full Lambek calculus with weakening is HAck-complete
by: Greati, Vitor, et al.
Published: (2024)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
by: Knop, Dušan, et al.
Published: (2017)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

Hard QBFs for Merge Resolution
by: Beyersdorff, Olaf, et al.
Published: (2020)

Semi-Algebraic Proof Systems for QBF
by: Beyersdorff, Olaf, et al.
Published: (2025)

Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
by: Higuchi, Joaquim Reizi
Published: (2026)

Unravelling Abstract Cyclic Proofs into Proofs by Induction
by: Grotenhuis, Lide, et al.
Published: (2026)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
by: Anttila, Aleksi, et al.
Published: (2025)

Locality, Consistency, and the Tractability Frontier
by: Simas, Tristan
Published: (2026)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
by: Filmus, Yuval, et al.
Published: (2024)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

The Fluted Fragment with Transitive Relations
by: Pratt-Hartmann, Ian, et al.
Published: (2020)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
by: Pilipczuk, Michał, et al.
Published: (2025)

Solutions of Word Equations over Partially Commutative Structures
by: Diekert, Volker, et al.
Published: (2016)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

A Sequent Calculus Perspective on Base-Extension Semantics (Technical Report)
by: Barroso-Nascimento, Victor, et al.
Published: (2025)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
by: van Brügge, Jan
Published: (2024)

A propositional cirquent calculus for computability logic
by: Japaridze, Giorgi
Published: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
by: Barroso-Nascimento, Victor, et al.
Published: (2025)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Punctually Standard and Nonstandard Models of Natural Numbers
by: Bazhenov, Nikolay, et al.
Published: (2026)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

Mechanised uniform interpolation for modal logics K, GL, and iSL
by: Férée, Hugo, et al.
Published: (2024)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)