Document Open Access Logo

Approximate F_2-Sketching of Valuation Functions

Authors Grigory Yaroslavtsev, Samson Zhou

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.69.pdf
  • Filesize: 0.61 MB
  • 21 pages

Document Identifiers

Author Details

Grigory Yaroslavtsev
  • Indiana University, Bloomington, IN, USA
  • The Alan Turing Institute, London, UK
Samson Zhou
  • Indiana University, Bloomington, IN, USA

Acknowledgements

We would like to thank Swagato Sanyal for multiple discussions leading to this paper, including the proof of Theorem 11 and Nikolai Karpov for his contributions to Section 3.1. We would also like to thank Amit Chakrabarti, Qin Zhang and anonymous reviewers for their comments.

Cite AsGet BibTex

Grigory Yaroslavtsev and Samson Zhou. Approximate F_2-Sketching of Valuation Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 69:1-69:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.69

Abstract

We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function f : F_2^n - > R with small expected squared error. We develop a general theory of linear sketching for such functions through which we analyze their dimension for most commonly studied types of valuation functions: additive, budget-additive, coverage, alpha-Lipschitz submodular and matroid rank functions. This gives a characterization of how many bits of information have to be stored about the input x so that one can compute f under additive updates to its coordinates. Our results are tight in most cases and we also give extensions to the distributional version of the problem where the input x in F_2^n is generated uniformly at random. Using known connections with dynamic streaming algorithms, both upper and lower bounds on dimension obtained in our work extend to the space complexity of algorithms evaluating f(x) under long sequences of additive updates to the input x presented as a stream. Similar results hold for simultaneous communication in a distributed setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • Sublinear algorithms
  • linear sketches
  • approximation algorithms

Metrics

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

Related Versions

References

  1. Dragan M Acketa. On the enumeration of matroids of rank-2. Zbornik radova Prirodnomatematickog fakulteta-Univerzitet u Novom Sadu, 8:83-90, 1978. Google Scholar
  2. Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff. New Characterizations in Turnstile Streams with Applications. In 31st Conference on Computational Complexity, CCC, pages 20:1-20:22, 2016. Google Scholar
  3. Noga Alon, Yossi Matias, and Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. Google Scholar
  4. Sepehr Assadi, Sanjeev Khanna, and Yang Li. Tight bounds for single-pass streaming complexity of the set cover problem. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 698-711, 2016. Google Scholar
  5. 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. Google Scholar
  6. 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, pages 239-246, 1997. Google Scholar
  7. Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden. Sketching valuation functions. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1025-1035, 2012. Google Scholar
  8. Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: massive data summarization on the fly. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pages 671-680, 2014. Google Scholar
  9. Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning Valuation Functions. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, pages 4.1-4.24, 2012. Google Scholar
  10. Maria-Florina Balcan and Nicholas J. A. Harvey. Learning submodular functions. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pages 793-802, 2011. Google Scholar
  11. MohammadHossein Bateni, Hossein Esfandiari, and Vahab S. Mirrokni. Almost Optimal Streaming Algorithms for Coverage Problems. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 13-23, 2017. Google Scholar
  12. Eric Blais and Abhinav Bommireddi. Testing Submodularity and Other Properties of Valuation Functions. In 8th Innovations in Theoretical Computer Science Conference, ITCS, pages 33:1-33:17, 2017. Google Scholar
  13. Eric Blais, Krzysztof Onak, Rocco Servedio, and Grigory Yaroslavtsev. Concise representations of discrete submodular functions, 2013. Google Scholar
  14. Jehoshua Bruck and Roman Smolensky. Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms. SIAM J. Comput., 21(1):33-42, 1992. Google Scholar
  15. Amit Chakrabarti and Anthony Wirth. Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1365-1373, 2016. Google Scholar
  16. Deeparnab Chakrabarty and Zhiyi Huang. Testing Coverage Functions. In Automata, Languages, and Programming - 39th International Colloquium, ICALP, Proceedings, Part I, pages 170-181, 2012. Google Scholar
  17. Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming Algorithms for Submodular Function Maximization. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP, Proceedings, Part I, pages 318-330, 2015. Google Scholar
  18. Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, and Homin K. Lee. Submodular functions are noise stable. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1586-1592, 2012. Google Scholar
  19. Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and Lopsided Set Disjointness via Information Theory. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX, and 16th International Workshop, RANDOM. Proceedings, pages 517-528, 2012. Google Scholar
  20. Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. On Streaming and Communication Complexity of the Set Cover Problem. In Distributed Computing - 28th International Symposium, DISC. Proceedings, pages 484-498, 2014. Google Scholar
  21. Yuval Emek and Adi Rosén. Semi-Streaming Set Cover. ACM Trans. Algorithms, 13(1):6:1-6:22, 2016. Google Scholar
  22. Vitaly Feldman and Pravesh Kothari. Learning Coverage Functions and Private Release of Marginals. In Proceedings of The 27th Conference on Learning Theory, COLT, pages 679-702, 2014. Google Scholar
  23. Vitaly Feldman, Pravesh Kothari, and Jan Vondrák. Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. In COLT 2013 - The 26th Annual Conference on Learning Theory, pages 711-740, 2013. Google Scholar
  24. Vitaly Feldman and Jan Vondrák. Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 923-942, 2015. Google Scholar
  25. Vitaly Feldman and Jan Vondrák. Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. SIAM J. Comput., 45(3):1129-1170, 2016. Google Scholar
  26. Gereon Frahling, Piotr Indyk, and Christian Sohler. Sampling in Dynamic Data Streams and Applications. Int. J. Comput. Geometry Appl., 18(1/2):3-28, 2008. Google Scholar
  27. Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab S. Mirrokni. Approximating submodular functions everywhere. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 535-544, 2009. Google Scholar
  28. Vince Grolmusz. On the Power of Circuits with Gates of Low L_1 Norms. Theor. Comput. Sci., 188(1-2):117-128, 1997. Google Scholar
  29. Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman. Privately Releasing Conjunctions and the Statistical Query Barrier. SIAM J. Comput., 42(4):1494-1520, 2013. Google Scholar
  30. Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. Towards Tight Bounds for the Streaming Set Cover Problem. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 371-383, 2016. Google Scholar
  31. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of Protocols for XOR Functions. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 282-288, 2016. Google Scholar
  32. Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching under Modular Updates. Electronic Colloquium on Computational Complexity (ECCC), 25:169, 2018. URL: https://eccc.weizmann.ac.il/report/2018/169.
  33. Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the Hamming distance problem. Inf. Process. Lett., 99(4):149-153, 2006. Google Scholar
  34. 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
  35. Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. Linear Sketching over F_2. In 33rd Computational Complexity Conference, CCC, pages 8:1-8:37, 2018. Google Scholar
  36. 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
  37. 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, pages 475-486, 2017. Google Scholar
  38. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  39. Troy Lee and Shengyu Zhang. Composition Theorems in Communication Complexity. In Automata, Languages and Programming, 37th International Colloquium, ICALP, Proceedings, Part I, pages 475-489, 2010. Google Scholar
  40. Ming Lam Leung, Yang Li, and Shengyu Zhang. Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models. CoRR, abs/1101.4555, 2011. URL: http://arxiv.org/abs/1101.4555.
  41. 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, pages 174-183, 2014. Google Scholar
  42. Yang Liu and Shengyu Zhang. Quantum and randomized communication complexity of XOR functions in the SMP model. Electronic Colloquium on Computational Complexity (ECCC), 20:10, 2013. Google Scholar
  43. Shachar Lovett. Recent Advances on the Log-Rank Conjecture in Communication Complexity. Bulletin of the EATCS, 112, 2014. Google Scholar
  44. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  45. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  46. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  47. Sofya Raskhodnikova and Grigory Yaroslavtsev. Learning pseudo-Boolean k-DNF and submodular functions. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1356-1368, 2013. Google Scholar
  48. Barna Saha and Lise Getoor. On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch. In Proceedings of the SIAM International Conference on Data Mining, SDM, pages 697-708, 2009. Google Scholar
  49. C. Seshadhri and Jan Vondrák. Is Submodularity Testable? Algorithmica, 69(1):1-25, 2014. Google Scholar
  50. Yaoyun Shi and Zhiqiang Zhang. Communication complexities of symmetric XOR functions. Quantum Inf. Comput, pages 0808-1762, 2008. Google Scholar
  51. Xiaoming Sun and Chengu Wang. Randomized Communication Complexity for Linear Algebra Problems over Finite Fields. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS, pages 477-488, 2012. Google Scholar
  52. 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
  53. 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, pages 658-667, 2013. Google Scholar
  54. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  55. Jan Vondrák. A note on concentration of submodular functions. CoRR, abs/1005.2791, 2010. URL: http://arxiv.org/abs/1005.2791.
  56. David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014. Google Scholar
  57. Grigory Yaroslavtsev and Samson Zhou. Approximate F_2-Sketching of Valuation Functions. CoRR, abs/1907.00524, 2019. URL: http://arxiv.org/abs/1907.00524.
  58. Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of Boolean functions. Theor. Comput. Sci., 411(26-28):2612-2618, 2010. 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 Imprint Privacy Contact