Document Open Access Logo

Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond

Authors Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.23.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Anup Bhattacharya
  • Indian Statistical Institute, Kolkata, India
Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Arijit Ghosh
  • Indian Statistical Institute, Kolkata, India
Gopinath Mishra
  • Indian Statistical Institute, Kolkata, India
Manaswi Paraashar
  • Indian Statistical Institute, Kolkata, India

Funding

  • Bhattacharya, Anup: Supported by SERB-National Post Doctoral Fellowship, India.
  • Ghosh, Arijit: Supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India.

Acknowledgements

The authors would like to thank Sudeshna Kolay and Arijit Bishnu for the many discussions in the early stages of this work.

Cite As Get BibTex

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.23

Abstract

The disjointness problem - where Alice and Bob are given two subsets of {1, … , n} and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be Θ(n), it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik–Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by d, we analyze how large can the deterministic and randomized communication complexities be, as a function of d and n. The d-sparse set disjointness problem, where the sets have size at most d, is one such set system with VC dimension d. The deterministic and the randomized communication complexities of the d-sparse set disjointness problem have been well studied and is known to be Θ (d log ({n}/{d})) and Θ(d), respectively, in the multi-round communication setting. In this paper, we address the question of whether the randomized communication complexity is always upper bounded by a function of the VC dimension of the set system, and does there always exist a gap between the deterministic and randomized communication complexity for set systems with small VC dimension. 
In this paper, we construct two natural set systems of VC dimension d, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be Θ̃(dlog (n/d)) for set systems of VC dimension d and this matches the deterministic upper bound for all set systems of VC dimension d. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension d such that both deterministic and randomized (one-way and multi-round) complexities for the set intersection problem can be as high as Θ(dlog (n/d)), and this is tight among all set systems of VC dimension d.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • Communication complexity
  • VC dimension
  • Sparsity
  • and Geometric Set System

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. J. Comput. Syst. Sci., 68(4):702-732, 2004. Google Scholar
  2. Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Beyond Set Disjointness: The Communication Complexity of Finding the Intersection. In ACM Symposium on Principles of Distributed Computing, PODC, pages 106-113, 2014. Google Scholar
  3. Bernard Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2001. Google Scholar
  4. Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and Lopsided Set Disjointness via Information Theory. In Proceedings of the RANDOM-APPROX, pages 517-528, 2012. Google Scholar
  5. Sariel Har-Peled. Geometric Approximation Algorithms. Number 173 in Mathematical Surveys and Monographs. American Mathematical Soc., 2011. Google Scholar
  6. Johan Håstad and Avi Wigderson. The Randomized Communication Complexity of Set Disjointness. Theory of Computing, 3(1):211-219, 2007. Google Scholar
  7. T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two Applications of Information Complexity. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC, pages 673-682, 2003. Google Scholar
  8. Bala Kalyanasundaram and Georg Schnitger. The Probabilistic Communication Complexity of Set Intersection. SIAM J. Discrete Math., 5(4):545-557, 1992. Google Scholar
  9. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, USA, 1996. Google Scholar
  10. Jiri Matousek. Geometric Discrepancy: An Illustrated Guide, volume 18. Springer Science & Business Media, 2009. Google Scholar
  11. Jiri Matousek. Lectures on Discrete Geometry, volume 212. Springer Science & Business Media, 2013. Google Scholar
  12. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci., 57(1):37-49, 1998. Google Scholar
  13. Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67-71, 1991. Google Scholar
  14. János Pach and Pankaj K Agarwal. Combinatorial Geometry, volume 37. John Wiley & Sons, 2011. Google Scholar
  15. Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. Google Scholar
  16. Alexander A. Razborov. On the Distributional Complexity of Disjointness. Theor. Comput. Sci., 106(2):385-390, 1992. Google Scholar
  17. Tim Roughgarden. Communication Complexity (for Algorithm Designers). Foundations and Trends in Theoretical Computer Science, 11(3-4):217-404, 2016. Google Scholar
  18. Mert Saglam and Gábor Tardos. On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 678-687, 2013. Google Scholar
  19. N. Sauer. On the Density of Families of Sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972. Google Scholar
  20. S. Shelah. A Combinatorial Problem, Stability and Order for Models and Theories in Infinitary Languages. Pacific Journal of Mathematics, 41:247-261, 1972. Google Scholar
  21. V. N. Vapnik and A. Y. Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971. Google Scholar
  22. Andrew Chi-Chih Yao. Some Complexity Questions Related to Distributive Computing (Preliminary Report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, STOC, pages 209-213, 1979. 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