:: Library Catalog

Imatge de la portada

Guardat en:

Dades bibliogràfiques
Autors principals:	Cai, Jin-Yi, Maran, Ashwin, Young, Ben
Format:	Preprint
Publicat:	2026
Matèries:	Computational Complexity
Accés en línia:	https://arxiv.org/abs/2601.23198
Etiquetes:	Afegir etiqueta Sense etiquetes, Sigues el primer a etiquetar aquest registre!

Ítems similars

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

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

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

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

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

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

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

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

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

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

A Dichotomy for Finite Abstract Simplicial Complexes
per: Meyer, Sebastian
Publicat: (2024)

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

Graph Homomorphisms and Universal Algebra
per: Bodirsky, Manuel
Publicat: (2026)

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

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

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

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

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

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

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

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

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

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

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

Geometry Matters in Planar Storyplans
per: Dobler, Alexander, et al.
Publicat: (2025)

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

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

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

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

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

The Parameterized Complexity of Geometric 1-Planarity
per: Firbas, Alexander
Publicat: (2026)

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

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

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

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

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

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

Dichotomy for orderings?
per: Kun, Gábor, et al.
Publicat: (2025)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
per: Kátay, Tamás, et al.
Publicat: (2023)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
per: Seppelt, Tim
Publicat: (2024)