Permutation Code Equivalence is not Harder than Graph Isomorphism when Hulls are Trivial
| Autor: | Magali Bardet, Ayoub Otmani, Mohamed Saeed-Taha |
|---|---|
| Přispěvatelé: | Equipe Combinatoire et algorithmes (CA - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Université de Rouen Normandie (UNIROUEN) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Subroutine 010102 general mathematics [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT] Orthogonal complement 010103 numerical & computational mathematics [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice 01 natural sciences Linear subspace Square matrix Combinatorics [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT] Computer Science - Data Structures and Algorithms Binary code Data Structures and Algorithms (cs.DS) 0101 mathematics Graph isomorphism Equivalence (formal languages) Mathematics Vector space |
| Zdroj: | 2019 IEEE International Symposium on Information Theory (ISIT) 2019 IEEE International Symposium on Information Theory (ISIT), Jul 2019, Paris, France. pp.2464-2468, ⟨10.1109/ISIT.2019.8849855⟩ ISIT |
| DOI: | 10.1109/ISIT.2019.8849855⟩ |
| Popis: | The paper deals with the problem of deciding if two finite-dimensional linear subspaces over an arbitrary field are identical up to a permutation of the coordinates. This problem is referred to as the permutation code equivalence. We show that given access to a subroutine that decides if two weighted undirected graphs are isomorphic, one may deterministically decide the permutation code equivalence provided that the underlying vector spaces intersect trivially with their orthogonal complement with respect to an arbitrary inner product. Such a class of vector spaces is usually called linear codes with trivial hulls. The reduction is efficient because it essentially boils down to computing the inverse of a square matrix of order the length of the involved codes. Experimental results obtained with randomly drawn binary codes having trivial hulls show that permutation code equivalence can be decided in a few minutes for lengths up to 50,000. Accepted to 2019 IEEE International Symposium on Information Theory |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|