{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,25]],"date-time":"2022-11-25T05:52:14Z","timestamp":1669355534956},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2022,12]]},"abstract":"Abstract<\/jats:title>The disjointness problem\u2014where Alice and Bob are given two\nsubsets of $$\\{1, \\dots, n\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n n<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and they have to check if their sets\nintersect\u2014is a central problem in the world of communication\ncomplexity. While both deterministic and randomized communication\ncomplexities for this problem are known to be $$\\Theta(n)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, it is\nalso known that if the sets are assumed to be drawn from some\nrestricted set systems then the communication complexity can be much\nlower. In this work, we explore how communication complexity\nmeasures change with respect to the complexity of the underlying set\nsystem. The complexity measure for the set system that we use in\nthis work is the Vapnik\u2014Chervonenkis (VC) dimension. More\nprecisely, on any set system with VC dimension bounded by d<\/jats:italic>, we\nanalyze how large can the deterministic and randomized communication\ncomplexities be, as a function of d<\/jats:italic> and n<\/jats:italic>. The d<\/jats:italic>-sparse set\ndisjointness problem, where the sets have size at most d<\/jats:italic>, is one\nsuch set system with VC dimension d<\/jats:italic>. The deterministic and the\nrandomized communication complexities of the d<\/jats:italic>-sparse set\ndisjointness problem have been well studied and are known to be\n$$\\Theta \\left( d \\log \\left({n}\/{d}\\right)\\right)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n \n d<\/mml:mi>\n log<\/mml:mo>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\Theta(d)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>,\nrespectively, in the multi-round communication setting. In this\npaper, we address the question of whether the randomized\ncommunication complexity of the disjointness problem is always upper\nbounded by a function of the VC dimension of the set system, and\ndoes there always exist a gap between the deterministic and\nrandomized communication complexities of the disjointness problem\nfor set systems with small VC dimension.<\/jats:p>We construct two natural set systems of VC dimension d<\/jats:italic>, motivated \nfrom geometry. Using these set systems, we show that the deterministic and \nrandomized communication complexity can be $$\\widetilde{\\Theta}\\left(d\\log \\left( n\/d \\right)\\right)$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n d<\/mml:mi>\n log<\/mml:mo>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for set systems of \nVC dimension d<\/jats:italic> and this matches the deterministic upper bound for all set \nsystems of VC dimension d<\/jats:italic>. We also study the deterministic and randomized \ncommunication complexities of the set intersection problem when sets belong to a set \nsystem of bounded VC dimension. We show that there exist set systems of \nVC dimension d<\/jats:italic> such that both deterministic and randomized (one-way and \nmulti-round) complexities for the set intersection problem can be as high \nas $$\\Theta\\left( d\\log \\left( n\/d \\right) \\right)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n \n d<\/mml:mi>\n log<\/mml:mo>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00037-022-00225-6","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T19:02:46Z","timestamp":1657047766000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Disjointness through the Lens of Vapnik\u2013Chervonenkis Dimension: Sparsity and Beyond"],"prefix":"10.1007","volume":"31","author":[{"given":"Anup","family":"Bhattacharya","sequence":"first","affiliation":[]},{"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[]},{"given":"Arijit","family":"Ghosh","sequence":"additional","affiliation":[]},{"given":"Gopinath","family":"Mishra","sequence":"additional","affiliation":[]},{"given":"Manaswi","family":"Paraashar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"225_CR1","doi-asserted-by":"crossref","unstructured":"Tom M. Apostol (1976). Introduction to Analytic Number Theory. Springer, New York, NY, 1st edition.","DOI":"10.1007\/978-1-4757-5579-4_1"},{"issue":"4","key":"225_CR2","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"TS Ziv Bar-Yossef","year":"2004","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar & D. Sivakumar (2004). An Information Statistics Approach to Data Stream and Communication Complexity. Journal of Computer and System Sciences 68(4), 702\u2013732.","journal-title":"Journal of Computer and System Sciences"},{"key":"225_CR3","doi-asserted-by":"crossref","unstructured":"Mark Braverman, Ankit Garg, Denis Pankratov & Omri Weinstein (2013). From information to exact communication. In Symposium on Theory of Computing Conference, STOC, 151\u2013160.","DOI":"10.1145\/2488608.2488628"},{"key":"225_CR4","first-page":"106","volume-title":"Beyond Set Disjointness: The Communication Complexity of Finding the Intersection","author":"Joshua Brody","year":"2014","unstructured":"Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff & Grigory Yaroslavtsev (2014). Beyond Set Disjointness: The Communication Complexity of Finding the Intersection. In ACM Symposium on Principles of Distributed Computing, PODC, 106\u2013113."},{"key":"225_CR5","doi-asserted-by":"crossref","unstructured":"Komaravolu Chandrasekharan (1968). Introduction to Analytic Number Theory. Springer, Berlin, Heidelberg, 1st edition.","DOI":"10.1007\/978-3-642-46124-8_1"},{"key":"225_CR6","doi-asserted-by":"crossref","unstructured":"Bernard Chazelle (2001). The Discrepancy Method: Randomness and Complexity. Cambridge University Press.","DOI":"10.1017\/CBO9780511626371"},{"key":"225_CR7","first-page":"517","volume-title":"Sparse and Lopsided Set Disjointness via Information Theory","author":"Anirban Dasgupta","year":"2012","unstructured":"Anirban Dasgupta, Ravi Kumar & D. Sivakumar (2012). Sparse and Lopsided Set Disjointness via Information Theory. In International Workshop on Randomization and Computation, RANDOM, 517\u2013528."},{"issue":"1","key":"225_CR8","doi-asserted-by":"publisher","first-page":"211","DOI":"10.4086\/toc.2007.v003a011","volume":"3","author":"Johan H\u00e5stad & Avi Wigderson","year":"2007","unstructured":"Johan H\u00e5stad & Avi Wigderson (2007). The Randomized Communication Complexity of Set Disjointness. Theory of Computing 3(1), 211\u2013219.","journal-title":"Theory of Computing"},{"key":"225_CR9","first-page":"673","volume-title":"Two Applications of Information Complexity","author":"TS Jayram","year":"2003","unstructured":"T. S. Jayram, Ravi Kumar & D. Sivakumar (2003). Two Applications of Information Complexity. In ACM Symposium on Theory of Computing, STOC, 673\u2013682."},{"issue":"4","key":"225_CR10","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"Bala Kalyanasundaram & Georg Schnitger","year":"1992","unstructured":"Bala Kalyanasundaram & Georg Schnitger (1992). The Probabilistic Communication Complexity of Set Intersection. SIAM Journal on Discrete Mathematics 5(4), 545\u2013557.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"225_CR11","volume-title":"Communication Complexity","author":"Eyal Kushilevitz & Noam Nisan","year":"1996","unstructured":"Eyal Kushilevitz & Noam Nisan (1996). Communication Complexity. Cambridge University Press."},{"key":"225_CR12","unstructured":"Jiri Matousek (2009). Geometric Discrepancy: An Illustrated Guide, volume 18. Springer Science & Business Media."},{"key":"225_CR13","unstructured":"Jiri Matousek (2013). Lectures on Discrete Geometry, volume 212. Springer Science & Business Media."},{"issue":"1","key":"225_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"Peter Bro Miltersen","year":"1998","unstructured":"Peter Bro Miltersen, Noam Nisan, Shmuel Safra & Avi Wigderson (1998). On Data Structures and Asymmetric Communication Complexity. Journal of Computer and System Sciences 57(1), 37\u201349.","journal-title":"Journal of Computer and System Sciences"},{"key":"225_CR15","doi-asserted-by":"crossref","unstructured":"Ilan Newman (1991). Private vs. Common Random Bits in Communication Complexity. Information Processing Letters 39(2), 67\u201371.","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"225_CR16","volume-title":"Combinatorial Geometry,","author":"J\u00e1nos Pach","year":"2011","unstructured":"J\u00e1nos Pach & Pankaj K. Agarwal (2011). Combinatorial Geometry, volume 37. John Wiley & Sons."},{"key":"225_CR17","volume-title":"Communication Complexity: and Applications","author":"Anup Rao & Amir Yehudayoff","year":"2020","unstructured":"Anup Rao & Amir Yehudayoff (2020). Communication Complexity: and Applications. Cambridge University Press."},{"issue":"2","key":"225_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"Alexander A Razborov","year":"1992","unstructured":"Alexander A. Razborov (1992). On the Distributional Complexity of Disjointness. Theoretical Computer Science 106(2), 385\u2013390.","journal-title":"Theoretical Computer Science"},{"key":"225_CR19","doi-asserted-by":"crossref","unstructured":"Guy Robin (1983). Estimation de la fonction de Tchebychef $$\\theta $$ sur le $$k$$-i\u00e8me nombre premier et grandes valeurs de la fonction $$\\omega (n)$$ nombre de diviseurs premiers de n. Acta Arithmetica 42(4), 367\u2013389.","DOI":"10.4064\/aa-42-4-367-389"},{"issue":"3\u20134","key":"225_CR20","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1561\/0400000076","volume":"11","author":"Tim Roughgarden","year":"2016","unstructured":"Tim Roughgarden (2016). Communication Complexity (for Algorithm Designers). Foundations and Trends in Theoretical Computer Science 11(3-4), 217\u2013404.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"225_CR21","first-page":"678","volume-title":"On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems","author":"Mert Saglam & G\u00e1bor Tardos","year":"2013","unstructured":"Mert Saglam & G\u00e1bor Tardos (2013). On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems. In IEEE Symposium on Foundations of Computer Science, FOCS, 678\u2013687."},{"issue":"1","key":"225_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"N. Sauer (1972). On the Density of Families of Sets. Journal of Combinatorial Theory, Series A 13(1), 145\u2013147.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"225_CR23","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"S. Shelah (1972). A Combinatorial Problem, Stability and Order for Models and Theories in Infinitary Languages. Pacific Journal of Mathematics 41, 247\u2013261.","journal-title":"Pacific Journal of Mathematics"},{"issue":"2","key":"225_CR24","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"V. N. Vapnik & A. Y. Chervonenkis (1971). On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and its Applications 16(2), 264\u2013280.","journal-title":"Theory of Probability and its Applications"},{"key":"225_CR25","first-page":"209","volume-title":"Some Complexity Questions Related to Distributive Computing (Preliminary Report)","author":"Andrew Chi-Chih Yao","year":"1979","unstructured":"Andrew Chi-Chih Yao (1979). Some Complexity Questions Related to Distributive Computing (Preliminary Report). In ACM Symposium on Theory of Computing, STOC, 209\u2013213."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00225-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00225-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00225-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T15:27:13Z","timestamp":1669303633000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00225-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["225"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00225-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"9 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}