@inproceedings{8b53a1867a76491c9342a2b20c3774c0,
title = "Matchgate Signatures Under Variable Permutations",
abstract = "In this work, we introduce the concept of permutable matchgate signatures and leverage it to establish dichotomy theorems for \#CSP and \#RD-CSP (D ≥ 3) on planar graphs without the variable ordering restriction. We also present a complete characterization of permutable matchgate signatures and their relationship to symmetric signatures. Besides, we give a sufficient and necessary condition for determining whether a matchgate signature retains its property under a certain variable permutation, which can be checked in polynomial time. In addition, we prove a dichotomy for Pl-\#RD-CSP (D ≥ 3), where the variable ordering restriction exists.",
keywords = "Computational Complexity, Counting CSP, Matchgate Signature",
author = "Boning Meng and Yicheng Pan",
note = "Publisher Copyright: {\textcopyright} 2025 Boning Meng and Yicheng Pan.; 36th International Symposium on Algorithms and Computation, ISAAC 2025 ; Conference date: 07-12-2025 Through 10-12-2025",
year = "2025",
doi = "10.4230/LIPIcs.ISAAC.2025.50",
language = "英语",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Ho-Lin Chen and Wing-Kai Hon and Tsai, \{Meng-Tsung \}",
booktitle = "36th International Symposium on Algorithms and Computation, ISAAC 2025",
address = "德国",
}