Document Type

Conference Proceeding

Publication Date

2014

Published In

Approximation, Randomization, And Combinatorial Optimization: Algorithms And Techniques (APPROX/RANDOM 2014)

Series Title

Leibniz International Proceedings In Informatics

Abstract

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.

Keywords

Hamming distance, communication complexity, information complexity

Published By

Schloss Dagstuhl

Editor(s)

K. Jansen, J. D. P. Rolim, N. R. Devanur, and C. Moore

Conference

APPROX/RANDOM'14

Conference Dates

September 4-6, 2014

Conference Location

Barcelona, Italy

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Download

Share

COinS