DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.50

Matchgate Signatures Under Variable Permutations

Authors: Boning Meng and Yicheng Pan

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

In this work, we introduce the concept of permutable matchgate signatures and leverage it to establish dichotomy theorems for #CSP and #R_D-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-#R_D-CSP (D ≥ 3), where the variable ordering restriction exists.

Cite as

Boning Meng and Yicheng Pan. Matchgate Signatures Under Variable Permutations. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meng_et_al:LIPIcs.ISAAC.2025.50,
  author =	{Meng, Boning and Pan, Yicheng},
  title =	{{Matchgate Signatures Under Variable Permutations}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.50},
  URN =		{urn:nbn:de:0030-drops-249587},
  doi =		{10.4230/LIPIcs.ISAAC.2025.50},
  annote =	{Keywords: Computational Complexity, Matchgate Signature, Counting CSP}
}

Document

Short Paper

DOI: 10.4230/LIPIcs.COSIT.2022.22

Abnormal Situation Simulation and Dynamic Causality Discovery in Urban Traffic Networks (Short Paper)

Authors: Yadi Wang, Yicheng Pan, Meng Ma, and Ping Wang

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)

Abstract

Various participants in urban traffic systems intertwine a highly complicated coupling network. An interpretable analysis of underlying correlations is one of the keys to understanding traffic anomalies. Unfortunately, abnormal situation analysis in real scenarios faces severe limitations in negative sample deficiency, data integrity, and verifiability. In view of this, we developed a simulation tool - the Traffic Anomaly Situation Simulator (TASS). Through configurable scripts, TASS simulates real traffic networks by road editing, data collection, and fault injection. Given the generated cases, we designed a dynamic causal discovery algorithm, Dycause-Traffic, to demonstrate the features of causality in traffic anomalies.

Cite as

Yadi Wang, Yicheng Pan, Meng Ma, and Ping Wang. Abnormal Situation Simulation and Dynamic Causality Discovery in Urban Traffic Networks (Short Paper). In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 22:1-22:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.COSIT.2022.22,
  author =	{Wang, Yadi and Pan, Yicheng and Ma, Meng and Wang, Ping},
  title =	{{Abnormal Situation Simulation and Dynamic Causality Discovery in Urban Traffic Networks}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{22:1--22:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.22},
  URN =		{urn:nbn:de:0030-drops-169077},
  doi =		{10.4230/LIPIcs.COSIT.2022.22},
  annote =	{Keywords: SUMO simulation, dynamic causality discovery, congestion propagation}
}

Search Results

Documents authored by Pan, Yicheng

Matchgate Signatures Under Variable Permutations

Abstract

Cite as

Abnormal Situation Simulation and Dynamic Causality Discovery in Urban Traffic Networks (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message