The communication complexity of gap Hamming distance. (English) Zbl 1253.68158
Summary: In the gap Hamming distance problem, two parties must determine whether their respective strings \(x,y\in\{0,1\}^n\) are at Hamming distance less than \(n/2-\sqrt n\) or greater than \(n/2+\sqrt n.\) In a recent tour de force, A. Chakrabarti and O. Regev [“An optimal lower bound on the communication complexity of gap-hamming-distance”, in: STOC ’11. Proceedings of the 43rd annual ACM symposium on theory of computing. New York, NY: Association for Computing Machinery (ACM). 51–60 (2011; doi:10.1145/1993636.1993644)] proved the long-conjectured \(\Omega(n)\) bound on the randomized communication complexity of this problem. In follow-up work,T. 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”, Technical Report TR11-051, Electron. Colloq. Comput. Complexity (ECCC) (2010), http://eccc.hpi-web.de/eccc-reports/2011/TR11-051/] discovered a simpler proof. We contribute a new proof, which is simpler yet and a page-and-a-half long.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | [1] NOGAALON ANDJOELH. SPENCER: The Probabilistic Method. John Wiley & Sons, 3rd edition, 2008. [doi:10.1002/9780470277331]201,203,205 |
| [2] | [2] LÁSZLÓBABAI, PÉTERFRANKL,ANDJÁNOSSIMON: Complexity classes in communication complexity theory.In Proc. 27th FOCS, pp. 337–347. IEEE Comp. Soc. Press, 1986. [doi:10.1109/SFCS.1986.15]199,200,203,204,205 THEORY OFCOMPUTING, Volume 8 (2012), pp. 197–208206 THECOMMUNICATIONCOMPLEXITY OFGAPHAMMINGDISTANCE |
| [3] | [3] PAULBEAME, TONIANNPITASSI, NATHANSEGERLIND,ANDAVIWIGDERSON: A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Comput. Complexity, 15(4):391–432, 2006. [doi:10.1007/s00037-007-0220-2]203 |
| [4] | [4] JOSHUABRODY ANDAMITCHAKRABARTI: A multi-round communication lower bound for gap Hamming and some consequences. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 358–368. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.31]198 |
| [5] | [5] JOSHUABRODY, AMITCHAKRABARTI, ODEDREGEV, THOMASVIDICK,ANDRONALD DE WOLF: Better gap-Hamming lower bounds via better round elimination. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 476–489. Springer, 2010. [doi:10.1007/978-3-642-15369-3_36]198,200 |
| [6] | [6] AMITCHAKRABARTI, GRAHAMCORMODE,ANDANDREWMCGREGOR: A near-optimal algorithm for estimating the entropy of a stream.ACM Trans. Algorithms, 6(3), 2010. [doi:10.1145/1798596.1798604]198 |
| [7] | [7] AMITCHAKRABARTI ANDODEDREGEV: An optimal lower bound on the communication complexity of gap-Hamming-distance.In Proc. 43rd STOC, pp. 51–60. ACM Press, 2011. [doi:10.1145/1993636.1993644]198,200,201,202 |
| [8] | [8] PIOTRINDYK ANDDAVIDP. WOODRUFF: Tight lower bounds for the distinct elements problem. In Proc. 44th FOCS, pp. 283–289. IEEE Comp. Soc. Press, 2003. [doi:10.1109/SFCS.2003.1238202] 198 |
| [9] | [9] RAHULJAIN ANDHARTMUTKLAUCK: The partition bound for classical communication complexity and query complexity. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 247–258. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.31]200 |
| [10] | [10] T. S. JAYRAM, RAVIKUMAR,ANDD. SIVAKUMAR: The one-way communication complexity of Hamming distance.Theory of Computing, 4(1):129–135, 2008. [doi:10.4086/toc.2008.v004a006] 198 |
| [11] | [11] BALAKALYANASUNDARAM ANDGEORGSCHNITGER: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992. [doi:10.1137/0405044] 198 |
| [12] | [12] EYALKUSHILEVITZ ANDNOAMNISAN: Communication complexity. Cambridge University Press, 1997. [doi:10.1017/CBO9780511574948]203 |
| [13] | [13] RANRAZ: Exponential separation of quantum and classical communication complexity. In Proc. 31st STOC, pp. 358–367. ACM Press, 1999. [doi:10.1145/301250.301343]200,201,202 |
| [14] | [14] ALEXANDERA. RAZBOROV: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385–390, 1992. [doi:10.1016/0304-3975(92)90260-M]198 THEORY OFCOMPUTING, Volume 8 (2012), pp. 197–208207 ALEXANDERA. SHERSTOV · Zbl 0787.68055 |
| [15] | [15] MICHELTALAGRAND: Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de L’IHÉS, 81(1):73–205, 1996. [doi:10.1007/BF02699376]201,205 |
| [16] | [16] TERENCETAO: Talagrand’s concentration inequality. Weblog entry, 2009.http://terrytao. wordpress.com/2009/06/09/talagrands-concentration-inequality/.201,203,206 |
| [17] | [17] THOMASVIDICK: 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. Technical Report TR11-051, Electron. Colloq. on Comput. Complexity (ECCC), 2010. Revised, 2011. [ECCC:TR11-051]198,200,201,202 |
| [18] | [18] DAVIDP. WOODRUFF: Optimal space lower bounds for all frequency moments. In Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’04), pp. 167–175, 2004. [ACM:982817]198 |
| [19] | [19] DAVIDP. WOODRUFF: The average-case complexity of counting distinct elements. In Proceedings of the Twelfth International Conference on Database Theory (ICDT), pp. 284–295, 2009. [doi:10.1145/1514894.1514928]198 |
| [20] | [20] ANDREWCHI-CHIHYAO: Lower bounds by probabilistic arguments. In Proc. 24th FOCS, pp. 420–428. IEEE Comp. Soc. Press, 1983. [doi:10.1109/SFCS.1983.30]198,199,203 AUTHOR Alexander A. Sherstov Assistant Professor University of California, Los Angeles sherstovcs ucla edu http://www.cs.ucla.edu/ sherstov ABOUT THE AUTHOR ALEXANDERA. SHERSTOVcompleted his Ph. D. in 2009 at theUniversity of Texas at Austinunder the direction ofAdam Klivans. After a postdoc atMicrosoft Research, Alexander recently joinedUCLAas an assistant professor of computer science. His research interests include computational complexity theory, computational learning theory, and quantum computing. THEORY OFCOMPUTING, Volume 8 (2012), pp. 197–208208 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
