Buchumschlag

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Roberson, David E., Seppelt, Tim
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Combinatorics Computational Complexity Discrete Mathematics Logic in Computer Science Optimization and Control
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
von: Seppelt, Tim
Veröffentlicht: (2024)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
von: Seppelt, Tim
Veröffentlicht: (2023)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
von: Kar, Prem Nigam, et al.
Veröffentlicht: (2024)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
von: Černý, Marek, et al.
Veröffentlicht: (2025)

Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
von: Neuen, Daniel, et al.
Veröffentlicht: (2026)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
von: Dwivedi, Prateek, et al.
Veröffentlicht: (2026)

Diffusion-Robust Optimization over Graphs
von: Aolaritei, Liviu, et al.
Veröffentlicht: (2026)

A Classification of Long-Refinement Graphs for Colour Refinement
von: Kiefer, Sandra, et al.
Veröffentlicht: (2025)

Approximate Graph Colouring and the Crystal with a Hollow Shadow
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2022)

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
von: Adler, Isolde, et al.
Veröffentlicht: (2025)

Restricted CSPs and F-free Digraph Algorithmics
von: Guzmán-Pro, Santiago, et al.
Veröffentlicht: (2025)

The Richness of CSP Non-redundancy
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

Gromov's Approximating Tree and the All-Pairs Bottleneck Paths Problem
von: Cornect, Anders, et al.
Veröffentlicht: (2024)

Testing Isomorphism of Graphs in Polynomial Time
von: Xue, Rui
Veröffentlicht: (2023)

Reconfiguring Graph Homomorphisms on the Sphere
von: Lee, Jae-Baek, et al.
Veröffentlicht: (2018)

Complexity Aspects of Homomorphisms of Ordered Graphs
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

Graph Homomorphisms and Universal Algebra
von: Bodirsky, Manuel
Veröffentlicht: (2026)

Arithmetic Circuits and Neural Networks for Regular Matroids
von: Hertrich, Christoph, et al.
Veröffentlicht: (2025)

Neural Networks and (Virtual) Extended Formulations
von: Hertrich, Christoph, et al.
Veröffentlicht: (2024)

Efficient approximation schemes for scheduling on a stochastic number of machines
von: Epstein, Leah, et al.
Veröffentlicht: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
von: Diaby, Moustapha
Veröffentlicht: (2016)

Existential Positive Transductions of Sparse Graphs
von: Mählmann, Nikolas, et al.
Veröffentlicht: (2026)

Separability Properties of Monadically Dependent Graph Classes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
von: Dreier, Jan, et al.
Veröffentlicht: (2024)

Hierarchies of Minion Tests for PCSPs through Tensors
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2022)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
von: Geniet, Colin, et al.
Veröffentlicht: (2026)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
von: Zhang, Tianwei, et al.
Veröffentlicht: (2024)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
von: Barto, Libor, et al.
Veröffentlicht: (2024)

Rice-like complexity lower bounds for Boolean and uniform automata networks
von: Goubault-Larrecq, Aliénor, et al.
Veröffentlicht: (2024)

The Unit Gap: How Sharing Works in Boolean Circuits
von: Krinkin, Kirill
Veröffentlicht: (2026)

On the Computational Complexity of Multi-Objective Ordinal Unconstrained Combinatorial Optimization
von: Figueira, José Rui, et al.
Veröffentlicht: (2024)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
von: Grüne, Christoph, et al.
Veröffentlicht: (2024)

First-Order Logic and Twin-Width for Some Geometric Graphs
von: Geniet, Colin, et al.
Veröffentlicht: (2025)

On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
von: Au, Yu Hin, et al.
Veröffentlicht: (2024)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
von: Grüne, Christoph, et al.
Veröffentlicht: (2023)

Advances in Algorithmic Meta Theorems
von: Siebertz, Sebastian, et al.
Veröffentlicht: (2024)

Characterizations of monadically dependent tree-ordered weakly sparse structures
von: Buffière, Hector, et al.
Veröffentlicht: (2026)

Decomposition horizons and a characterization of stable hereditary classes of graphs
von: Braunfeld, Samuel, et al.
Veröffentlicht: (2022)

Epsilon-saturation for stable graphs and Littlestone classes
von: Malliaris, Maryanthe, et al.
Veröffentlicht: (2025)

On first-order transductions of classes of graphs
von: Braunfeld, Samuel, et al.
Veröffentlicht: (2022)