Document Open Access Logo

A Direct-Sum Theorem for Read-Once Branching Programs

Authors Anup Rao, Makrand Sinha

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.44.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Anup Rao
Makrand Sinha

Cite As Get BibTex

Anup Rao and Makrand Sinha. A Direct-Sum Theorem for Read-Once Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.44

Abstract

We study a direct-sum question for read-once branching programs. If M(f) denotes the minimum average memory required to compute a function f(x_1,x_2, ..., x_n)  how much memory is required to compute f on k independent inputs that arrive in parallel? We show that when the inputs are sampled independently from some domain X and M(f) = Omega(n), then computing the value of f on k streams requires average memory at least Omega(k * M(f)/n).

Our results are obtained by defining new ways to measure the information complexity of read-once branching programs. We define two such measures: the transitional and cumulative information content. We prove that any read-once branching program with transitional information content I can be simulated using average memory O(n(I+1)). On the other hand, if every read-once branching program with cumulative information content I can be simulated with average memory O(I+1), then computing f on k inputs requires average memory at least Omega(k * (M(f)-1)).

Subject Classification

Keywords
  • Direct-sum
  • Information complexity
  • Streaming Algorithms

Metrics

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

References

  1. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137-147, 1999. Google Scholar
  2. Chrisil Arackaparambil, Joshua Brody, and Amit Chakrabarti. Functional monitoring without monotonicity. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, volume 5555 of Lecture Notes in Computer Science, pages 95-106. Springer Berlin Heidelberg, 2009. Google Scholar
  3. Brian Babcock and Chris Olston. Distributed top-k monitoring. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, SIGMOD'03, pages 28-39, New York, NY, USA, 2003. ACM. Google Scholar
  4. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An Information Statistics Approach to Data Stream and Communication Complexity. In FOCS, pages 209-218, 2002. Google Scholar
  5. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM J. Comput., 42(3):1327-1363, 2013. Google Scholar
  6. Mark Braverman. Interactive information complexity. In STOC, pages 505-524, 2012. Google Scholar
  7. Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. A tight bound for set disjointness in the message-passing model. In FOCS, pages 668-677, 2013. Google Scholar
  8. Mark Braverman and Ankit Garg. Public vs Private Coin in Bounded-Round Information. In ICALP, pages 502-513, 2014. Google Scholar
  9. Mark Braverman and Anup Rao. Information equals amortized communication. In FOCS, pages 748-757, 2011. Google Scholar
  10. Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 107-117, 2003. Google Scholar
  11. Arkadev Chattopadhyay, Jaikumar Radhakrishnan, and Atri Rudra. Topology matters in communication. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 631-640, 2014. Google Scholar
  12. G. Cormode, S. Muthukrishnan, and Wei Zhuang. What’s different: Distributed, continuous monitoring of duplicate-resilient aggregates on data streams. In Data Engineering, 2006. ICDE'06. Proceedings of the 22nd International Conference on, pages 57-57, April 2006. Google Scholar
  13. Graham Cormode. Sketching streams through the net: Distributed approximate query tracking. In VLDB, pages 13-24, 2005. Google Scholar
  14. Graham Cormode and Minos Garofalakis. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In SIGMOD, pages 25-36, 2005. Google Scholar
  15. Graham Cormode, S. Muthukrishnan, and Ke Yi. Algorithms for distributed functional monitoring. ACM Trans. Algorithms, 7(2):21:1-21:20, March 2011. Google Scholar
  16. Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. Optimal sampling from distributed streams. In Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'10, pages 77-86, New York, NY, USA, 2010. ACM. Google Scholar
  17. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006. Google Scholar
  18. Pavol Duris and Jose D.P. Rolim. Lower bounds on the multiparty communication complexity. Journal of Computer and System Sciences, 56(1):90-95, 1998. Google Scholar
  19. Funda Ergun and Hossein Jowhari. On distance to monotonicity and longest increasing subsequence of a data stream. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'08, pages 730-736, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics. Google Scholar
  20. Anna Gál and Parikshit Gopalan. Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence. SIAM J. Comput., 39(8):3463-3479, August 2010. Google Scholar
  21. Anat Ganor, Gillat Kol, and Ran Raz. Exponential Separation of Information and Communication for Boolean Functions. Electronic Colloquium on Computational Complexity (ECCC), 21:113, 2014. Google Scholar
  22. André Gronemeier. Asymptotically optimal lower bounds on the nih-multi-party information complexity of the and-function and disjointness. In STACS 2009, pages 505-516, 2009. Google Scholar
  23. Sudipto Guha and Zhiyi Huang. Revisiting the direct sum theorem and space lower bounds in random order streams. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, volume 5555 of Lecture Notes in Computer Science, pages 513-524. Springer Berlin Heidelberg, 2009. Google Scholar
  24. Prahladh Harsha, Rahul Jain, David A. McAllester, and Jaikumar Radhakrishnan. The communication complexity of correlation. IEEE Transactions on Information Theory, 56(1):438-449, 2010. URL: http://dx.doi.org/10.1109/TIT.2009.2034824.
  25. Zengfeng Huang, Božidar Radunović, Milan Vojnović, and Qin Zhang. Communication complexity of approximate maximum matching in distributed graph data. In STACS, 2015. Google Scholar
  26. Ram Keralapura, Graham Cormode, and Jeyashankher Ramamirtham. Communication-efficient distributed monitoring of thresholded counts. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD'06, pages 289-300, New York, NY, USA, 2006. ACM. Google Scholar
  27. Amit Manjhi, Vladislav Shkapenyuk, Kedar Dhamdhere, and Christopher Olston. Finding (recently) frequent items in distributed data streams. In Proceedings of the 21st International Conference on Data Engineering, ICDE'05, pages 767-778, Washington, DC, USA, 2005. IEEE Computer Society. Google Scholar
  28. Marco Molinaro, David P. Woodruff, and Grigory Yaroslavtsev. Beating the direct sum theorem in communication complexity with implications for sketching. In SODA, pages 1738-1756, 2013. Google Scholar
  29. Jeff M. Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'12, pages 486-501. SIAM, 2012. Google Scholar
  30. Izchak Sharfman, Assaf Schuster, and Daniel Keren. A geometric approach to monitoring threshold functions over distributed data streams. ACM Transactions on Database Systems, 32(4), November 2007. Google Scholar
  31. Izchak Sharfman, Assaf Schuster, and Daniel Keren. Shape sensitive geometric monitoring. In Proceedings of the Twenty-seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'08, pages 301-310, New York, NY, USA, 2008. ACM. Google Scholar
  32. David Woodruff. Optimal space lower bounds for all frequency moments. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'04, pages 167-175, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics. Google Scholar
  33. David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In STOC, pages 941-960, 2012. Google Scholar
  34. David P. Woodruff and Qin Zhang. An optimal lower bound for distinct elements in the message passing model. In SODA, pages 718-733, 2014. Google Scholar
  35. A.D. Wyner. The common information of two dependent random variables. IEEE Transactions on Information Theory, 21(2):163-179, 1975. 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