The Closure of LCD-to-GI Reductions via Generalized Inner Products
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914590641618944 |
|---|---|
| author | Ishizuka, Keita |
| author_facet | Ishizuka, Keita |
| contents | The Permutation Equivalence Problem (PEP) for linear codes is a fundamental problem in coding theory and cryptography. A recent reduction shows that PEP for Linear Complementary Dual (LCD) codes reduces to Graph Isomorphism (GI) via orthogonal projectors, but is restricted to codes with trivial hull. We prove that this approach extends to bilinear forms $M = aI + bJ$, and that no other nondegenerate symmetric form yields a valid reduction. A code is reducible if and only if its hull dimension is at most $1$ with an explicit condition on the hull vector; in characteristic $2$, only LCD codes are reducible. This establishes the closure of the orthogonal projector method. We derive exact enumeration formulas via character sums over quadratic forms and provide a polynomial-time reduction algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23120 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Closure of LCD-to-GI Reductions via Generalized Inner Products Ishizuka, Keita Information Theory Combinatorics The Permutation Equivalence Problem (PEP) for linear codes is a fundamental problem in coding theory and cryptography. A recent reduction shows that PEP for Linear Complementary Dual (LCD) codes reduces to Graph Isomorphism (GI) via orthogonal projectors, but is restricted to codes with trivial hull. We prove that this approach extends to bilinear forms $M = aI + bJ$, and that no other nondegenerate symmetric form yields a valid reduction. A code is reducible if and only if its hull dimension is at most $1$ with an explicit condition on the hull vector; in characteristic $2$, only LCD codes are reducible. This establishes the closure of the orthogonal projector method. We derive exact enumeration formulas via character sums over quadratic forms and provide a polynomial-time reduction algorithm. |
| title | The Closure of LCD-to-GI Reductions via Generalized Inner Products |
| topic | Information Theory Combinatorics |
| url | https://arxiv.org/abs/2605.23120 |