Document Open Access Logo

Noisy Boolean Hidden Matching with Applications

Authors Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.91.pdf
  • Filesize: 0.83 MB
  • 19 pages

Document Identifiers

Author Details

Michael Kapralov
  • EPFL, Lausanne, Switzerland
Amulya Musipatla
  • Carnegie Mellon University, Pittsburgh, PA, USA
Jakab Tardos
  • EPFL, Lausanne, Switzerland
David P. Woodruff
  • Carnegie Mellon University, Pittsburgh, PA, USA
Samson Zhou
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite As Get BibTex

Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. Noisy Boolean Hidden Matching with Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 91:1-91:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.91

Abstract

The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et al. [STOC'07], has played an important role in lower bounds for graph problems in the streaming model (e.g., subgraph counting, maximum matching, MAX-CUT, Schatten p-norm approximation). The BHM problem typically leads to Ω(√n) space lower bounds for constant factor approximations, with the reductions generating graphs that consist of connected components of constant size. The related Boolean Hidden Hypermatching (BHH) problem provides Ω(n^{1-1/t}) lower bounds for 1+O(1/t) approximation, for integers t ≥ 2. The corresponding reductions produce graphs with connected components of diameter about t, and essentially show that long range exploration is hard in the streaming model with an adversarial order of updates. 
In this paper we introduce a natural variant of the BHM problem, called noisy BHM (and its natural noisy BHH variant), that we use to obtain stronger than Ω(√n) lower bounds for approximating a number of the aforementioned problems in graph streams when the input graphs consist only of components of diameter bounded by a fixed constant. 
We next introduce and study the graph classification problem, where the task is to test whether the input graph is isomorphic to a given graph. As a first step, we use the noisy BHM problem to show that the problem of classifying whether an underlying graph is isomorphic to a complete binary tree in insertion-only streams requires Ω(n) space, which seems challenging to show using either BHM or BHH.

Subject Classification

ACM Subject Classification
  • Theory of computation → Lower bounds and information complexity
Keywords
  • Boolean Hidden Matching
  • Lower Bounds
  • Communication Complexity
  • Streaming Algorithms

Metrics

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

Related Versions

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 459-467, 2012. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 5-14, 2012. Google Scholar
  3. Sepehr Assadi. Personal communication, 2021. Google Scholar
  4. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1723-1742, 2017. Google Scholar
  5. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1345-1364, 2016. Google Scholar
  6. Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu. Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 354-364, 2020. Google Scholar
  7. Sepehr Assadi and Vishvajeet N. Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. In STOC: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 612-625, 2021. Google Scholar
  8. Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM J. Comput., 38(1):366-384, 2008. Google Scholar
  9. 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
  10. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 173-182, 2015. Google Scholar
  11. Mark Braverman and Anup Rao. Information equals amortized communication. IEEE Trans. Inf. Theory, 60(10):6058-6069, 2014. Google Scholar
  12. Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, and Samson Zhou. Structural results on matching estimation with applications to streaming. Algorithmica, 81(1):367-392, 2019. Google Scholar
  13. Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1326-1344, 2016. Google Scholar
  14. Rajesh Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh. Parameterized streaming: Maximal matching and vertex cover. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1234-1251, 2015. Google Scholar
  15. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Approximability of all boolean csps in the dynamic streaming setting. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2021. (to appear). Google Scholar
  16. Chi-Ning Chou, Sasha Golovnev, and Santhoshini Velusamy. Optimal streaming approximations for all boolean max-2csps and max-ksat. In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 330-341, 2020. Google Scholar
  17. Michael Crouch and Daniel S. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 96-104, 2014. Google Scholar
  18. Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Testable properties in general graphs and random order streaming. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, 2020. Google Scholar
  19. Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. ACM Trans. Algorithms, 14(4):48:1-48:23, 2018. Google Scholar
  20. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. Google Scholar
  21. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 38(5):1709-1727, 2008. Google Scholar
  22. Dmitry Gavinsky, Julia Kempe, and Ronald de Wolf. Exponential separation of quantum and classical one-way communication complexity for a boolean function. CoRR, abs/quant-ph/0607174, 2006. Google Scholar
  23. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695-1708, 2008. Google Scholar
  24. Sudipto Guha, Andrew McGregor, and David Tench. Vertex and hyperedge connectivity in dynamic graph streams. In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS, pages 241-247, 2015. Google Scholar
  25. Venkatesan Guruswami and Runzhou Tao. Streaming hardness of unique games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 5:1-5:12, 2019. Google Scholar
  26. Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. Streaming complexity of approximating max 2csp and max acyclic subgraph. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 81, pages 8:1-8:19, 2017. Google Scholar
  27. Zengfeng Huang and Pan Peng. Dynamic graph stream algorithms in o(n) space. Algorithmica, 81(5):1965-1987, 2019. Google Scholar
  28. Rahul Jain, Attila Pereszlényi, and Penghui Yao. A direct product theorem for bounded-round public-coin randomized communication complexity. CoRR, abs/1201.1666, 2012. Google Scholar
  29. Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 68-80. IEEE Computer Society, 1988. Google Scholar
  30. John Kallaugher, Michael Kapralov, and Eric Price. The sketching complexity of graph and hypergraph counting. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 556-567, 2018. URL: https://doi.org/10.1109/FOCS.2018.00059.
  31. John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1778-1797, 2017. Google Scholar
  32. Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1679-1697, 2013. Google Scholar
  33. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 734-751, 2014. Google Scholar
  34. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1263-1282, 2015. Google Scholar
  35. Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. (1+ω(1))-approximation to MAX-CUT requires linear space. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1703-1722, 2017. Google Scholar
  36. Michael Kapralov and Dmitry Krachun. An optimal space lower bound for approximating MAX-CUT. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 277-288, 2019. URL: https://doi.org/10.1145/3313276.3316364.
  37. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM J. Comput., 46(1):456-477, 2017. Google Scholar
  38. Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, and Jakab Tardos. Space efficient approximation to maximum matching size from uniform edge samples. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1753-1772, 2020. Google Scholar
  39. Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. Noisy boolean hidden matching with applications. CoRR, abs/2107.02578, 2021. Google Scholar
  40. Michael Kapralov and David P. Woodruff. Spanners and sparsifiers in dynamic streams. In ACM Symposium on Principles of Distributed Computing, PODC, pages 272-281, 2014. Google Scholar
  41. Iordanis Kerenidis and Ran Raz. The one-way communication complexity of the boolean hidden matching problem. CoRR, abs/quant-ph/0607173, 2006. Google Scholar
  42. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS, pages 367-376, 2015. Google Scholar
  43. Yi Li and David P. Woodruff. On approximating functions of the singular values in a stream. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 726-739, 2016. Google Scholar
  44. Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. Testable bounded degree graph properties are random order streamable. In 44th International Colloquium on Automata, Languages, and Programming, ICALP, pages 131:1-131:14, 2017. Google Scholar
  45. Jelani Nelson and Huacheng Yu. Optimal lower bounds for distributed and streaming spanning forest computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1844-1860, 2019. Google Scholar
  46. Ami Paz and Gregory Schwartzman. A (2 + ε-approximation for maximum weight matching in the semi-streaming model. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2153-2161, 2017. Google Scholar
  47. Xiaoming Sun and David P. Woodruff. Tight bounds for graph problems in insertion streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 435-448, 2015. Google Scholar
  48. Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 11-25, 2011. 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