Buchumschlag

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	de Rezende, Susanna F., Engström, David, Ghannane, Yassine, Risse, Kilian
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity 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

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

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

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

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

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

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

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

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
von: Hakoniemi, Tuomas, et al.
Veröffentlicht: (2024)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
von: van Brügge, Jan
Veröffentlicht: (2024)

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

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

Direct Sums for Parity Decision Trees
von: Besselman, Tyler, et al.
Veröffentlicht: (2024)

A Rust-to-Lean Verification Pipeline with AI Provers: An Experience Report
von: Klaus, Natalia, 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)

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

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

Logics for the Relational Syllogistic
von: Pratt-Hartmann, Ian, et al.
Veröffentlicht: (2008)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

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

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)

A Quadratic Lower Bound for Simulation
von: Groote, Jan Friso, et al.
Veröffentlicht: (2024)

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

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

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

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

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

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

Algorithmic Trading Strategy Development and Optimisation
von: Yuan, Owen Nyo Wei, et al.
Veröffentlicht: (2026)

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

ProofBridge: Auto-Formalization of Natural Language Proofs in Lean via Joint Embeddings
von: Jana, Prithwish, et al.
Veröffentlicht: (2025)

On Sampling Lower Bounds for Polynomials
von: Khodabandeh, Mohammad Mahdi, et al.
Veröffentlicht: (2026)

Non-Compact Proofs
von: Artemov, Sergei
Veröffentlicht: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
von: Saha, Barna, et al.
Veröffentlicht: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
von: Salas, Jesus
Veröffentlicht: (2025)

Yanasse: Finding New Proofs from Deep Vision's Analogies, Part 1
von: Linhares, Alexandre
Veröffentlicht: (2026)