Publication

Sign-Rank of k-Hamming Distance is Constant

2025

Résumé

We prove that the sign-rank of the k Hamming Distance matrix on n bits is 2O(k), independent of the number of bits n. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (random 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the sign-rank should depend on n. This conjecture would have qualitatively separated margin from sign-rank (or, equivalently, bounded-error from unbounded-error randomized communication). In fact, our technique gives constant sign-rank upper bounds for all matrices which reduce to k-Hamming Distance, as well as large-margin matrices recently shown to be irreducible to k-Hamming Distance.

Source officielle

https://infoscience.epfl.ch/entities/publication/de145522-a11c-4279-9a71-db4a6478a2bf

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2025

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/de145522-a11c-4279-9a71-db4a6478a2bf

À propos de ce résultat

Concepts associés (32)

Code de Hamming

Un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d'une erreur si elle ne porte que sur une lettre du message. Un code de Hamming est parfait : pour une longueur de code donnée il n'existe pas d'autre code plus compact ayant la même capacité de correction. En ce sens son rendement est maximal. Il existe une famille de codes de Hamming ; le plus célèbre et le plus simple après le code de répétition binaire de dimension trois et de longueur un est sans doute le code binaire de paramètres [7,4,3].

Distance de Hamming

La distance de Hamming est une notion mathématique, définie par Richard Hamming, et utilisée en informatique, en traitement du signal et dans les télécommunications. Elle joue un rôle important en théorie algébrique des codes correcteurs. Elle permet de quantifier la différence entre deux séquences de symboles. C'est une distance au sens mathématique du terme. À deux suites de symboles de même longueur, elle associe le nombre de positions où les deux suites diffèrent.

Code linéaire

En mathématiques, plus précisément en théorie des codes, un code linéaire est un code correcteur ayant une certaine propriété de linéarité. Plus précisément, un tel code est structuré comme un sous-espace vectoriel d'un espace vectoriel de dimension finie sur un corps fini. L'espace vectoriel fini utilisé est souvent F2n le terme usuel est alors celui de code linéaire binaire. Il est décrit par trois paramètres [n, k, δ] . n décrit la dimension de l'espace qui le contient. Cette grandeur est appelée longueur du code.

Afficher plus

Publications associées (4)

Afficher plus

Sign-Rank of k-Hamming Distance is Constant

Chattez avec Graph Search

A Topological Approach to Magnetic Nulls

Deep Linear Networks for Regression Are Implicitly Regularized Towards Flat Minima

Molecular associative memory: An associative memory framework with exponential storage capacity for DNA computing