Document Open Access Logo

Optimality of Linear Sketching Under Modular Updates

Authors Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.13.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Kaave Hosseini
  • University of California, San Diego, USA
Shachar Lovett
  • University of California, San Diego, USA
Grigory Yaroslavtsev
  • Indiana University, Bloomington, USA

Funding

  • Hosseini, Kaave: Supported by NSF grant CCF-1614023.
  • Lovett, Shachar: Supported by NSF grant CCF-1614023.

Cite As Get BibTex

Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.13

Abstract

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in n dimensions, the existence of efficient streaming algorithms which can process Omega(n^2) updates implies efficient linear sketching algorithms with comparable cost. This improves upon the previous work of Li, Nguyen and Woodruff [Yi Li et al., 2014] and Ai, Hu, Li and Woodruff [Yuqing Ai et al., 2016] which required a triple-exponential number of updates to achieve a similar result for updates over integers. We extend our results to updates modulo p for integers p >= 2, and to approximation instead of exact computation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Sketching and sampling
Keywords
  • communication complexity
  • linear sketching
  • streaming algorithm

Metrics

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

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 2012, Kyoto, Japan, January 17-19, 2012, 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 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 5-14, 2012. Google Scholar
  3. Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff. New Characterizations in Turnstile Streams with Applications. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:22, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.20.
  4. Noga Alon, Yossi Matias, and Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. URL: https://doi.org/10.1006/jcss.1997.1545.
  5. 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 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1723-1742, 2017. Google Scholar
  6. 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 2016, Arlington, VA, USA, January 10-12, 2016, pages 1345-1364, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch93.
  7. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication Complexity of Simultaneous Messages. SIAM J. Comput., 33(1):137-166, 2003. URL: https://doi.org/10.1137/S0097539700375944.
  8. László Babai and Peter G. Kimmel. Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. In Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997, pages 239-246, 1997. Google Scholar
  9. 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 2015, Portland, OR, USA, June 14-17, 2015, pages 173-182, 2015. Google Scholar
  10. Mei-Chu Chang et al. A polynomial bound in Freiman’s theorem. Duke mathematical journal, 113(3):399-419, 2002. Google Scholar
  11. 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 2016, Arlington, VA, USA, January 10-12, 2016, pages 1326-1344, 2016. Google Scholar
  12. Rajesh Hemant 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 2015, San Diego, CA, USA, January 4-6, 2015, pages 1234-1251, 2015. Google Scholar
  13. Ernie Croot and Olof Sisask. A probabilistic technique for finding almost-periods of convolutions. Geometric and functional analysis, 20(6):1367-1396, 2010. Google Scholar
  14. Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff. Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 397-399, 2016. Google Scholar
  15. Martin Farach-Colton and Meng-Tsung Tsai. Tight Approximations of Degeneracy in Large Graphs. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 429-440, 2016. Google Scholar
  16. Sumit Ganguly. Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract). In Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, pages 204-215, 2008. Google Scholar
  17. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of Protocols for XOR Functions. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 282-288, 2016. URL: https://doi.org/10.1109/FOCS.2016.38.
  18. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307-323, 2006. URL: https://doi.org/10.1145/1147954.1147955.
  19. William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability, pages 189-206, 1984. Google Scholar
  20. Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. Linear Sketching over F₂. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 8:1-8:37, 2018. Google Scholar
  21. Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, and Mobin Yahyazadeh. Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 475-486, 2017. URL: https://doi.org/10.1109/FOCS.2017.50.
  22. Christian Konrad. Maximum Matching in Turnstile Streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 840-852, 2015. Google Scholar
  23. Yi Li, Huy L. Nguyen, and David P. Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 174-183, 2014. URL: https://doi.org/10.1145/2591796.2591812.
  24. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. URL: https://doi.org/10.1145/2627692.2627694.
  25. Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. Densest Subgraph in Dynamic Graph Streams. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 472-482, 2015. Google Scholar
  26. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  27. Noam Nisan. Psuedorandom Generators for Space-Bounded Computation. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 204-212, 1990. Google Scholar
  28. Tomasz Schoen and Olof Sisask. Roth theorem for four variables and additive structures in sums of sparse sets. In Forum of Mathematics, Sigma, volume 4. Cambridge University Press, 2016. Google Scholar
  29. Yaoyun Shi and Zhiqiang Zhang. Communication complexities of symmetric XOR functions. Quantum Inf. Comput, pages 0808-1762, 2008. Google Scholar
  30. Justin Thaler. Semi-Streaming Algorithms for Annotated Graph Streams. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 59:1-59:14, 2016. Google Scholar
  31. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 658-667, 2013. URL: https://doi.org/10.1109/FOCS.2013.76.
  32. David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014. URL: https://doi.org/10.1561/0400000060.
  33. Penghui Yao. Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent. Chicago J. Theor. Comput. Sci., 2016, 2016. URL: http://cjtcs.cs.uchicago.edu/articles/2016/12/contents.html.
  34. Grigory Yaroslavtsev and Samson Zhou. Approximate F₂-Sketching of Valuation Functions. In submission to ITCS'19, available at http://grigory.us/files/approx-linsketch.pdf., 2018. 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