Buchumschlag

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cai, Jin-Yi, Maran, Ashwin, Young, Ben
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2024)

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2025)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
von: Fan, Austen, et al.
Veröffentlicht: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
von: Komarath, Balagopal, et al.
Veröffentlicht: (2025)

A Dichotomy for Maximum PCSPs on Graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

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

Dichotomies for \#CSP on graphs that forbid a clique as a minor
von: Meng, Boning, et al.
Veröffentlicht: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
von: Bai, Tian, et al.
Veröffentlicht: (2026)

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

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
von: MIT Hardness Group, et al.
Veröffentlicht: (2026)

A Dichotomy for Finite Abstract Simplicial Complexes
von: Meyer, Sebastian
Veröffentlicht: (2024)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
von: Baril, Ambroise, et al.
Veröffentlicht: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
von: Hörsch, Florian, et al.
Veröffentlicht: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

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

Complexity Dichotomies for Graph Homomorphism Problems on Restricted Classes
von: SÉRGIO DE ANDRADE, PAULO
Veröffentlicht: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
von: Dvořák, Pavel, et al.
Veröffentlicht: (2022)

Dynamic Planar Graph Isomorphism is in DynFO
von: Datta, Samir, et al.
Veröffentlicht: (2026)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
von: Abboud, Amir, et al.
Veröffentlicht: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Geometry Matters in Planar Storyplans
von: Dobler, Alexander, et al.
Veröffentlicht: (2025)

Proper vs Improper Quantum PAC learning
von: Nayak, Ashwin, et al.
Veröffentlicht: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
von: Roberson, David E., et al.
Veröffentlicht: (2023)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

Recognizing 2-Layer and Outer $k$-Planar Graphs
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
von: Bhargav, C. S., et al.
Veröffentlicht: (2025)

Linear Planar 3-SAT and Its Applications in Planning
von: Desbois, Victorien, et al.
Veröffentlicht: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

The Parameterized Complexity of Geometric 1-Planarity
von: Firbas, Alexander
Veröffentlicht: (2026)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

Recovery Reductions, Conjectures, and Barriers
von: Nareddy, Tejas, et al.
Veröffentlicht: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
von: Hamm, Thekla, et al.
Veröffentlicht: (2026)

A General Framework for Low Soundness Homomorphism Testing
von: Mittal, Tushant, et al.
Veröffentlicht: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
von: Lowe, Angus, et al.
Veröffentlicht: (2022)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
von: Shakiba, Yousef, et al.
Veröffentlicht: (2025)

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

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
von: Majumdar, Angshul
Veröffentlicht: (2026)