DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2025.86

Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting

Authors: Shuai Shao and Zhuxiao Tang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

We discover a novel connection between two classical mathematical notions, Eulerian orientations and Hadamard codes by studying the counting problem of Eulerian orientations (#EO) with local constraint functions imposed on vertices. We present two special classes of constraint functions and a chain reaction algorithm, and show that the #EO problem defined by each class alone is polynomial-time solvable by the algorithm. These tractable classes of functions are defined inductively, and quite remarkably the base level of these classes is characterized perfectly by the well-known Hadamard code. Thus, we establish a novel connection between counting Eulerian orientations and coding theory. We also prove a #P-hardness result for the #EO problem when constraint functions from the two tractable classes appear together.

Cite as

Shuai Shao and Zhuxiao Tang. Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 86:1-86:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shao_et_al:LIPIcs.ITCS.2025.86,
  author =	{Shao, Shuai and Tang, Zhuxiao},
  title =	{{Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{86:1--86:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.86},
  URN =		{urn:nbn:de:0030-drops-227146},
  doi =		{10.4230/LIPIcs.ITCS.2025.86},
  annote =	{Keywords: Eulerian orientations, Hadamard codes, Counting problems, Tractable classes}
}

Search Results

Documents authored by Tang, Zhuxiao

Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting

Abstract

Cite as

Thanks for your feedback!

Could not send message