Cover Image

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Barto, Libor, Butti, Silvia, Dalmau, Víctor
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
by: Boreale, Michele, et al.
Published: (2019)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Algorithms and Complexity of Difference Logic
by: Dabrowski, Konrad K., et al.
Published: (2024)

Subgraph Isomorphism: Prolog vs. Conventional
by: Yin, Claire Y., et al.
Published: (2025)

Efficient Coalgebraic Partition Refinement
by: Dorsch, Ulrich, et al.
Published: (2017)

Derivation and Verification of Array Sorting by Merging, and its Certification in Dafny
by: Carbonell, Juan Pablo, et al.
Published: (2025)

Model checking with temporal graphs and their derivative
by: Bui-Xuan, Binh-Minh, et al.
Published: (2026)

MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
by: Kleest-Meißner, Sarah, et al.
Published: (2022)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

Asymptotically Smaller Encodings for Graph Problems and Scheduling
by: Subercaseaux, Bernardo
Published: (2025)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Exact Exploration
by: Blass, Andreas, et al.
Published: (2024)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

Ranked Enumeration for MSO on Trees via Knowledge Compilation
by: Amarilli, Antoine, et al.
Published: (2023)

Direct Access for Answers to Conjunctive Queries with Aggregation
by: Eldar, Idan, et al.
Published: (2023)

Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy
by: Berkholz, Christoph, et al.
Published: (2025)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

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

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

Color Refinement for Relational Structures
by: Scheidt, Benjamin, et al.
Published: (2024)

A bargain for mergesorts -- How to prove your mergesort correct and stable, almost for free
by: Cohen, Cyril, et al.
Published: (2024)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
by: de Colnet, Alexis, et al.
Published: (2026)

Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
by: Leutgeb, Lorenz, et al.
Published: (2022)

Verified Purely Functional Catenable Real-Time Deques
by: Viennot, Jules, et al.
Published: (2025)

The Model Counting Competitions 2021-2023
by: Fichte, Johannes K., et al.
Published: (2025)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)