Publication

Equality Is Far Weaker Than Constant-Cost Communication

2025

Résumé

We exhibit an n-bit communication problem with a constant-cost randomized protocol but which requires nΩ(1) deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized"using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, Göös, Harms, and Hatami (STOC 2025), that constant-cost communication does not reduce to the k-Hamming Distance hierarchy.

Source officielle

https://infoscience.epfl.ch/entities/publication/898dab15-4be1-474a-b7c5-1027ccd8ca93

À 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/898dab15-4be1-474a-b7c5-1027ccd8ca93

À propos de ce résultat

Concepts associés (19)

Communications optiques en espace libre

Dans le domaine des télécommunications, les communications optiques en espace libre (en anglais Free Space Optics ou FSO) constituent une technologie optique de communications qui fait appel à la propagation de la lumière (spectre visible ou infrarouge) en espace libre, afin de transmettre des données entre deux points distants. Cette technologie présente un intérêt lorsqu'une connexion physique par le biais de câble ou de fibre optique est inadaptée, en particulier pour des raisons de coûts.

AppleTalk

est un protocole de communication d'Apple. Il est employé par les ordinateurs Macintosh depuis 1984, d'abord en tant que partie intégrante du réseau LocalTalk puis en tant que protocole autonome (couches 3 à 5), le plus souvent au sein de trames Ethernet, l'ensemble étant baptisé EtherTalk. Utilisé jusqu'à la version Mac OS X 10.5.x du système d'exploitation, il a disparu dans Mac OS X 10.6. Le protocole TCP/IP et la technologie Bonjour ont définitivement pris le relais. LocalTalk EtherType Catégorie:Protoc

Fiber-optic communication

Fiber-optic communication is a method of transmitting information from one place to another by sending pulses of infrared or visible light through an optical fiber. The light is a form of carrier wave that is modulated to carry information. Fiber is preferred over electrical cabling when high bandwidth, long distance, or immunity to electromagnetic interference is required. This type of communication can transmit voice, video, and telemetry through local area networks or across long distances.

Afficher plus