Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cai, Jin-Yi, Maran, Ashwin, Young, Ben
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
by: Cai, Jin-Yi, et al.
Published: (2025)

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

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
by: Komarath, Balagopal, et al.
Published: (2025)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
by: Lee, Jae-Baek, et al.
Published: (2018)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, et al.
Published: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
by: Eagling-Vose, Tala, et al.
Published: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
by: MIT Hardness Group, et al.
Published: (2026)

A Dichotomy for Finite Abstract Simplicial Complexes
by: Meyer, Sebastian
Published: (2024)

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

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

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Graph Homomorphisms and Universal Algebra
by: Bodirsky, Manuel
Published: (2026)

Complexity Dichotomies for Graph Homomorphism Problems on Restricted Classes
by: SÉRGIO DE ANDRADE, PAULO
Published: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

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

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

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Geometry Matters in Planar Storyplans
by: Dobler, Alexander, et al.
Published: (2025)

Proper vs Improper Quantum PAC learning
by: Nayak, Ashwin, et al.
Published: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
by: Zhuk, Dmitriy
Published: (2024)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

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

Recovery Reductions, Conjectures, and Barriers
by: Nareddy, Tejas, et al.
Published: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
by: Hamm, Thekla, et al.
Published: (2026)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
by: Lowe, Angus, et al.
Published: (2022)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
by: Shakiba, Yousef, et al.
Published: (2025)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

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