Eulerian orientations and Hadamard codes: A novel connection via counting
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917267537657856 |
|---|---|
| author | Shao, Shuai Tang, Zhuxiao |
| author_facet | Shao, Shuai Tang, Zhuxiao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02612 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Eulerian orientations and Hadamard codes: A novel connection via counting Shao, Shuai Tang, Zhuxiao Computational Complexity F.0 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. |
| title | Eulerian orientations and Hadamard codes: A novel connection via counting |
| topic | Computational Complexity F.0 |
| url | https://arxiv.org/abs/2411.02612 |