Buchumschlag

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	de Rezende, Susanna F., Nordström, Jakob, Risse, Kilian, Sokolov, Dmitry
Format:	Preprint
Veröffentlicht:	2019
Schlagworte:	Computational Complexity Logic in Computer Science Combinatorics F.2.2, F.1.3, I.2.3, F.4.1 F.2.2; F.1.3; I.2.3; F.4.1
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2024)

Supercritical Tradeoffs for Monotone Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2024)

On bounded depth proofs for Tseitin formulas on the grid; revisited
von: Håstad, Johan, et al.
Veröffentlicht: (2022)

On the Satisfaction Probabilities of $k$-CNF Formulas
von: Tantau, Till
Veröffentlicht: (2022)

A Rust-to-Lean Verification Pipeline with AI Provers: An Experience Report
von: Klaus, Natalia, et al.
Veröffentlicht: (2026)

Unravelling Abstract Cyclic Proofs into Proofs by Induction
von: Grotenhuis, Lide, et al.
Veröffentlicht: (2026)

OnlineProver: Experience with a Visualisation Tool for Teaching Formal Proofs
von: Perháč, Ján, et al.
Veröffentlicht: (2025)

A Coq-based Axiomatization of Tarski's Mereogeometry
von: Barlatier, Patrick, et al.
Veröffentlicht: (2025)

SPARQL in N3: SPARQL CONSTRUCT as a rule language for the Semantic Web (Extended Version)
von: Arndt, Dörthe, et al.
Veröffentlicht: (2025)

A Sequent Calculus for General Inductive Definitions
von: Eede, Robbe Van den, et al.
Veröffentlicht: (2026)

Mechanized HOL Reasoning in Set Theory
von: Guilloud, Simon, et al.
Veröffentlicht: (2024)

Incomplete Descriptions and Qualified Definiteness
von: Więckowski, Bartosz
Veröffentlicht: (2024)

Term Orders for Optimistic Lambda-Superposition
von: Bentkamp, Alexander, et al.
Veröffentlicht: (2025)

Metric Equational Theories
von: Mardare, Radu, et al.
Veröffentlicht: (2025)

Canonical for Automated Theorem Proving in Lean
von: Norman, Chase, et al.
Veröffentlicht: (2025)

Implementing Dependent Type Theory Inhabitation and Unification
von: Norman, Chase, et al.
Veröffentlicht: (2026)

FastLEC: Parallel Datapath Equivalence Checking with Hybrid Engines
von: Zhang, Xindi, et al.
Veröffentlicht: (2025)

The Relational Machine Calculus
von: Barrett, Chris, et al.
Veröffentlicht: (2024)

Understanding Syllogistic Reasoning in LLMs from Formal and Natural Language Perspectives
von: Poddar, Aheli, et al.
Veröffentlicht: (2025)

Modelling Distributed Applications with Mixed-Choice Stateful Typestates
von: Parrinha, Francisco, et al.
Veröffentlicht: (2026)

Discernment is all you need
von: Fuenmayor, David
Veröffentlicht: (2026)

Experiments with Choice in Dependently-Typed Higher-Order Logic
von: Ranalter, Daniel, et al.
Veröffentlicht: (2024)

Tractable and Intractable Entailment Problems in Separation Logic with Inductively Defined Predicates
von: Echenim, Mnacho, et al.
Veröffentlicht: (2023)

Solving Quantified Modal Logic Problems by Translation to Classical Logics
von: Steen, Alexander, et al.
Veröffentlicht: (2022)

Inductive First-Order Formula Synthesis by ASP: A Case Study in Invariant Inference
von: Yang, Ziyi, et al.
Veröffentlicht: (2026)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
von: Antonelli, Melissa, et al.
Veröffentlicht: (2025)

Bidirectional Interpolation for the Lambda-Calculus -- Revisiting and Formalising Craig-Čubrić Interpolation
von: Bertrand, Meven Lennon, et al.
Veröffentlicht: (2026)

The Hamiltonian Syllogistic
von: Pratt-Hartmann, Ian
Veröffentlicht: (2010)

Test Case Features as Hyper-heuristics for Inductive Programming
von: McDaid, Edward, et al.
Veröffentlicht: (2024)

TPTP World Infrastructure for Non-classical Logics
von: Steen, Alexander, et al.
Veröffentlicht: (2025)

Min-CSPs on Complete Instances
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

Instruction and Solution Probabilities as Heuristics for Inductive Programming
von: McDaid, Edward, et al.
Veröffentlicht: (2025)

Oruga: An Avatar of Representational Systems Theory
von: Raggi, Daniel, et al.
Veröffentlicht: (2025)

Incremental Selection of Most-Filtering Conjectures and Proofs of the Selected Conjectures
von: Ngouonou, Jovial Cheukam, et al.
Veröffentlicht: (2025)

Efficient Solving of Quantified Inequality Constraints over the Real Numbers
von: Ratschan, Stefan
Veröffentlicht: (2002)

Alpay Algebra II: Identity as Fixed-Point Emergence in Categorical Data
von: Alpay, Faruk
Veröffentlicht: (2025)