Publication

Equality Is Far Weaker Than Constant-Cost Communication

2025

Abstract

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.

Official source

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

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2025

Abstract

Official source

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

About this result

Related concepts (19)

Free-space optical communication

Free-space optical communication (FSO) is an optical communication technology that uses light propagating in free space to wirelessly transmit data for telecommunications or computer networking. "Free space" means air, outer space, vacuum, or something similar. This contrasts with using solids such as optical fiber cable. The technology is useful where the physical connections are impractical due to high costs or other considerations. Optical communications, in various forms, have been used for thousands of years.

AppleTalk

AppleTalk is a discontinued proprietary suite of networking protocols developed by Apple Computer for their Macintosh computers. AppleTalk includes a number of features that allow local area networks to be connected with no prior setup or the need for a centralized router or server of any sort. Connected AppleTalk-equipped systems automatically assign addresses, update the distributed namespace, and configure any required inter-networking routing. AppleTalk was released in 1985 and was the primary protocol used by Apple devices through the 1980s and 1990s.

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.