Imagen de Portada

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	de Rezende, Susanna F., Potechin, Aaron, Risse, Kilian
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity F.2.2; F.1.3; I.2.3; F.4.1
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
por: Conneryd, Jonas, et al.
Publicado: (2025)

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

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

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

Supercritical Tradeoffs for Monotone Circuits
por: Göös, Mika, et al.
Publicado: (2024)

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

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
por: Antonelli, Melissa, et al.
Publicado: (2025)

A Rust-to-Lean Verification Pipeline with AI Provers: An Experience Report
por: Klaus, Natalia, et al.
Publicado: (2026)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
por: Conneryd, Jonas, et al.
Publicado: (2025)

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

On the Complexity of Determinations
por: Hellerstein, Joseph M.
Publicado: (2026)

OnlineProver: Experience with a Visualisation Tool for Teaching Formal Proofs
por: Perháč, Ján, et al.
Publicado: (2025)

A Coq-based Axiomatization of Tarski's Mereogeometry
por: Barlatier, Patrick, et al.
Publicado: (2025)

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

Logics for the Relational Syllogistic
por: Pratt-Hartmann, Ian, et al.
Publicado: (2008)

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

A Sequent Calculus for General Inductive Definitions
por: Eede, Robbe Van den, et al.
Publicado: (2026)

Mechanized HOL Reasoning in Set Theory
por: Guilloud, Simon, et al.
Publicado: (2024)

Incomplete Descriptions and Qualified Definiteness
por: Więckowski, Bartosz
Publicado: (2024)

Term Orders for Optimistic Lambda-Superposition
por: Bentkamp, Alexander, et al.
Publicado: (2025)

Metric Equational Theories
por: Mardare, Radu, et al.
Publicado: (2025)

Canonical for Automated Theorem Proving in Lean
por: Norman, Chase, et al.
Publicado: (2025)

Implementing Dependent Type Theory Inhabitation and Unification
por: Norman, Chase, et al.
Publicado: (2026)

Direct Sums for Parity Decision Trees
por: Besselman, Tyler, et al.
Publicado: (2024)

FastLEC: Parallel Datapath Equivalence Checking with Hybrid Engines
por: Zhang, Xindi, et al.
Publicado: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
por: Bodnar, Levente
Publicado: (2024)

Notes on CSPs and Polymorphisms
por: Brady, Zarathustra
Publicado: (2022)

The Relational Machine Calculus
por: Barrett, Chris, et al.
Publicado: (2024)

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

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
por: Saha, Barna, et al.
Publicado: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
por: Salas, Jesus
Publicado: (2025)

A correspondence between the time and space complexity
por: Latkin, Ivan V.
Publicado: (2023)

Understanding Syllogistic Reasoning in LLMs from Formal and Natural Language Perspectives
por: Poddar, Aheli, et al.
Publicado: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
por: Burke, Kyle, et al.
Publicado: (2024)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
por: Rossman, Benjamin
Publicado: (2024)

Modelling Distributed Applications with Mixed-Choice Stateful Typestates
por: Parrinha, Francisco, et al.
Publicado: (2026)

Discernment is all you need
por: Fuenmayor, David
Publicado: (2026)

Experiments with Choice in Dependently-Typed Higher-Order Logic
por: Ranalter, Daniel, et al.
Publicado: (2024)

Tractable and Intractable Entailment Problems in Separation Logic with Inductively Defined Predicates
por: Echenim, Mnacho, et al.
Publicado: (2023)

Solving Quantified Modal Logic Problems by Translation to Classical Logics
por: Steen, Alexander, et al.
Publicado: (2022)