Cover Image

Dichotomies for \#CSP on graphs that forbid a clique as a minor

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meng, Boning, Pan, Yicheng
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Matchgate signatures under variable permutations
by: Meng, Boning, et al.
Published: (2025)

On a tree-based variant of bandwidth and forbidding simple topological minors
by: Jacob, Hugo, et al.
Published: (2025)

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

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

The Counting General Dominating Set Framework
by: Zheng, Jiayi, et al.
Published: (2026)

From an odd arity signature to a Holant dichotomy
by: Meng, Boning, et al.
Published: (2025)

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
by: Meng, Boning, et al.
Published: (2025)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

Strongly Refuting Random CSP without Literals
by: Chan, Siu On, et al.
Published: (2026)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)

Towards infinite PCSP: a dichotomy for monochromatic cliques
by: Banakh, Demian, et al.
Published: (2026)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
by: Bhangale, Amey, et al.
Published: (2025)

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

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

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

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
by: Guruswami, Venkatesan, et al.
Published: (2024)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

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

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
by: Barto, Libor, et al.
Published: (2021)

Constructing self-referential instances for the clique problem
by: Li, Jiaqi, et al.
Published: (2026)

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

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Dichotomy results for classes of countable graphs
by: Cipriani, Vittorio, et al.
Published: (2025)

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

Algorithmic methods of finite discrete structures. Graph clique problem
by: Kurapov, Sergey, et al.
Published: (2024)

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

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

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Low-degree phase transitions for detecting a planted clique in sublinear time
by: Mardia, Jay, et al.
Published: (2024)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

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

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