Partition Bound Is Quadratically Tight for Product Distributions

Authors Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.135.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Prahladh Harsha
Rahul Jain
Jaikumar Radhakrishnan

Cite AsGet BibTex

Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan. Partition Bound Is Quadratically Tight for Product Distributions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 135:1-135:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.135

Abstract

Let f: {0,1}^n*{0,1}^n -> {0,1} be a 2-party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2), where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely, CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2). The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let g: {0,1}^n -> {0,1} be a function. For every bit-wise product distribution mu on {0,1}^n, we show that QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2), where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.
Keywords
  • partition bound
  • product distribution
  • communication complexity
  • query complexity

Metrics

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

References

  1. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM J. Comput., 42(3):1327-1363, 2013. (Preliminary Version in 42nd STOC, 2010). URL: http://dx.doi.org/10.1137/100811969.
  2. Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, and Jérémie Roland. Relative discrepancy does not separate information and communication complexity. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Proc. 42nd International Colloq. of Automata, Languages and Programming (ICALP), Part I, volume 9134 of LNCS, pages 506-516. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_41.
  3. Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communication. In Proc. 55th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 176-185, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.27.
  4. Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communication for boolean functions. In Proc. 47th ACM Symp. on Theory of Computing (STOC), pages 557-566, 2015. URL: http://dx.doi.org/10.1145/2746539.2746572.
  5. Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of communication and external information. In Proc. 48th ACM Symp. on Theory of Computing (STOC), 2016. (to appear). Google Scholar
  6. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication vs. partition number. Technical Report TR15-169, Elect. Colloq. on Comput. Complexity (ECCC), 2015. URL: http://eccc.hpi-web.de/report/2015/169.
  7. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. In Proc. 47th ACM Symp. on Theory of Computing (STOC), pages 257-266, 2015. URL: http://dx.doi.org/10.1145/2746539.2746596.
  8. Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan. Partition bound is quadratically tight for product distributions, 2016. URL: http://arxiv.org/abs/1512.01968.
  9. Rahul Jain and Hartmut Klauck. The partition bound for classical communication complexity and query complexity. In Proc. 25th IEEE Conf. on Computational Complexity, pages 247-258, 2010. http://arxiv.org/abs/0910.4266, URL: http://dx.doi.org/10.1109/CCC.2010.31.
  10. Rahul Jain and Penghui Yao. A strong direct product theorem in terms of the smooth rectangle bound, 2012. URL: http://arxiv.org/abs/1209.0263.
  11. Gillat Kol. Interactive compression for product distributions. In Proc. 48th ACM Symp. on Theory of Computing (STOC), 2016. (to appear). Google Scholar
  12. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. URL: http://dx.doi.org/10.1017/CBO9780511574948.
  13. Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Combinatorica, 15(4):557-565, 1995. (Preliminary version in 35th FOCS, 1994). URL: http://dx.doi.org/10.1007/BF01192527.
  14. Clifford D. Smyth. Reimer’s inequality and Tardos' conjecture. In Proc. 34th ACM Symp. on Theory of Computing (STOC), pages 218-221, 2002. URL: http://dx.doi.org/10.1145/509907.509942.
  15. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proc. 11th ACM Symp. on Theory of Computing (STOC), pages 209-213, 1979. URL: http://dx.doi.org/10.1145/800135.804414.
  16. Andrew Chi-Chih Yao. Lower bounds by probabilistic arguments (extended abstract). In Proc. 24th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 420-428, 1983. URL: http://dx.doi.org/10.1109/SFCS.1983.30.
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