2026-07-23T05:42:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4717 2024-03-06T10:35:18Z ddc:004 open_access

The Information Complexity of Hamming Distance Blais, Eric Brody, Joshua Ghazi, Badih Hamming distance communication complexity information complexity The Hamming distance function Ham_{n,d} returns 1 on all pairs of inputs x and y that differ in at most d coordinates and returns 0 otherwise. We initiate the study of the information complexity of the Hamming distance function. We give a new optimal lower bound for the information complexity of the Ham_{n,d} function in the small-error regime where the protocol is required to err with probability at most epsilon < d/n. We also give a new conditional lower bound for the information complexity of Ham_{n,d} that is optimal in all regimes. These results imply the first new lower bounds on the communication complexity of the Hamming distance function for the shared randomness two-way communication model since Pang and El-Gamal (1986). These results also imply new lower bounds in the areas of property testing and parity decision tree complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Blais and Joshua Brody and Badih Ghazi 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.465 urn:nbn:de:0030-drops-47174 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.465 eng https://creativecommons.org/licenses/by/3.0/legalcode