Document Open Access Logo

The Information Complexity of Hamming Distance

Authors Eric Blais, Joshua Brody, Badih Ghazi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.465.pdf
  • Filesize: 0.61 MB
  • 25 pages

Document Identifiers

Author Details

Eric Blais
Joshua Brody
Badih Ghazi

Cite As Get BibTex

Eric Blais, Joshua Brody, and Badih Ghazi. The Information Complexity of Hamming Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 465-489, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.465

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.

Subject Classification

Keywords
  • Hamming distance
  • communication complexity
  • information complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. In Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 209-218, 2002. Google Scholar
  2. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In STOC, pages 67-76, 2010. Google Scholar
  3. Eric Blais. Testing juntas nearly optimally. In Proceedings of the 41st annual ACM symposium on Theory of computing, pages 151-158. ACM, 2009. Google Scholar
  4. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  5. Mark Braverman. Interactive information complexity. In Proc. 44th Annual ACM Symposium on the Theory of Computing, 2012. Google Scholar
  6. Mark Braverman and Anup Rao. Information equals amortized communication. In FOCS, pages 748-757, 2011. Google Scholar
  7. Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of Gap-Hamming-Distance. SIAM Journal on Computing, 41(5):1299-1317, 2012. Google Scholar
  8. Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Yao. Informational complexity and the direct sum problem for simultaneous message complexity. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 270-278. IEEE, 2001. Google Scholar
  9. Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012. Google Scholar
  10. Tomas Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan. Amortized communication complexity. SIAM Journal on Computing, 24(4):736-750, 1995. Google Scholar
  11. Dmitry Gavinsky, Julia Kempe, and Ronald de Wolf. Quantum communication cannot simulate a public coin. arXiv preprint quant-ph/0411051, 2004. Google Scholar
  12. Johan Håstad and Avi Wigderson. The randomized communication complexity of set disjointness. Theory of Computing, 3(1):211-219, 2007. Google Scholar
  13. Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the hamming distance problem. Inform. Process. Lett., 99:149-153, 2006. Google Scholar
  14. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Disc. Math., 5(4):547-557, 1992. Google Scholar
  15. Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, and David Xiao. Lower bounds on information complexity via zero-communication protocols and applications. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 500-509. IEEE, 2012. Google Scholar
  16. Marco Molinaro, David P Woodruff, and Grigory Yaroslavtsev. Beating the direct sum theorem in communication complexity with implications for sketching. In SODA, pages 1738-1756. SIAM, 2013. Google Scholar
  17. Ryan O'Donnell. Hardness amplification within NP. J. Comput. Syst. Sci., 69(1):68-94, 2004. Google Scholar
  18. King F Pang and Abbas El Gamal. Communication complexity of computing the hamming distance. SIAM Journal on Computing, 15(4):932-947, 1986. Google Scholar
  19. Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In STOC, pages 468-474, 1992. Google Scholar
  20. Mert Sağlam and Gábor Tardos. On the communication complexity of sparse set disjointness and exists-equal problems. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 678-687. IEEE, 2013. Google Scholar
  21. Alexander A Sherstov. The communication complexity of gap hamming distance. Theory of Computing, 8(1):197-208, 2012. Google Scholar
  22. Thomas Vidick. A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the gap-hamming-distance problem. Chicago Journal of Theoretical Computer Science, 1, 2012. Google Scholar
  23. Emanuele Viola and Avi Wigderson. Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(1):137-168, 2008. Google Scholar
  24. David P Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the 44th symposium on Theory of Computing, pages 941-960. ACM, 2012. Google Scholar
  25. Andrew C. Yao. Some complexity questions related to distributive computing. In Proc. 11th Annual ACM Symposium on the Theory of Computing, pages 209-213, 1979. Google Scholar
  26. Andrew Chi-Chih Yao. On the power of quantum fingerprinting. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 77-81. ACM, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact