Document Open Access Logo

One-Way Communication Complexity and Non-Adaptive Decision Trees

Authors Nikhil S. Mande, Swagato Sanyal, Suhail Sherif

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.49.pdf
  • Filesize: 0.82 MB
  • 24 pages

Document Identifiers

Author Details

Nikhil S. Mande
  • CWI, Amsterdam, The Netherlands
Swagato Sanyal
  • Indian Institute of Technology, Kharagpur, India
Suhail Sherif
  • Vector Institute, Toronto, Canada

Funding

  • Mande, Nikhil S.: Supported by the Dutch Research Council (NWO) through QuantERA project QuantAlgo 680-91-034.
  • Sanyal, Swagato: Supported by an ISIRD Grant from Sponsored Research and Industrial Consultancy, IIT Kharagpur. Part of this work was done while the author was at NTU and CQT, and supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13.

Acknowledgements

Swagato Sanyal thanks Prahladh Harsha and Jaikumar Radhakrishnan for pointing out the reference [Peter Frankl and Norihide Tokushige, 1999], and Srijita Kundu for pointing out the reference [Hartmut Klauck, 2000]. N.S.M. thanks Ronald de Wolf for useful discussions. We thank Justin Thaler for pointing out a bug from an earlier version of the paper, and Arnab Maiti for helpful comments. We thank anonymous reviewers for helpful comments and suggestions, including an improvement of the value b from 4 to 2 in Theorem 1.3.

Cite As Get BibTex

Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.49

Abstract

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. More generally, we show the following when the gadget is Inner Product on 2b input bits for all b ≥ 2, denoted IP.  
- If f is a total Boolean function that depends on all of its n input bits, then the bounded-error one-way quantum communication complexity of f∘IP equals Ω(n(b-1)). 
- If f is a partial Boolean function, then the deterministic one-way communication complexity of f∘IP is at least Ω(b ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{dt}^ → (f) denotes non-adaptive decision tree complexity of f.  To prove our quantum lower bound, we first show a lower bound on the VC-dimension of f∘IP. We then appeal to a result of Klauck [STOC'00], which immediately yields our quantum lower bound. Our deterministic lower bound relies on a combinatorial result independently proven by Ahlswede and Khachatrian [Adv. Appl. Math.'98], and Frankl and Tokushige [Comb.'99].
It is known due to a result of Montanaro and Osborne [arXiv'09] that the deterministic one-way communication complexity of f∘XOR equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following when the inner gadget is the AND function on 2 input bits.  
- There exists a function for which even the quantum non-adaptive AND decision tree complexity of f is exponentially large in the deterministic one-way communication complexity of f∘AND. 
- However, for symmetric functions f, the non-adaptive AND decision tree complexity of f is at most quadratic in the (even two-way) communication complexity of f∘AND.  In view of the first bullet, a lower bound on non-adaptive AND decision tree complexity of f does not lift to a lower bound on one-way communication complexity of f∘AND. The proof of the first bullet above uses the well-studied Odd-Max-Bit function. For the second bullet, we first observe a connection between the one-way communication complexity of f and the Möbius sparsity of f, and then give a lower bound on the Möbius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result.
It is well known that the rank of the communication matrix of a function F is an upper bound on its deterministic one-way communication complexity. This bound is known to be tight for some F. However, in our final result we show that this is not the case when F = f∘AND. More precisely we show that for all f, the deterministic one-way communication complexity of F = f∘AND is at most (rank(M_{F}))(1 - Ω(1)), where M_{F} denotes the communication matrix of F.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Oracles and decision trees
Keywords
  • Decision trees
  • communication complexity
  • composed Boolean functions

Metrics

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

Related Versions

References

  1. Rudolf Ahlswede and Levon H Khachatrian. The diametric theorem in hamming spaces—optimal anticodes. Advances in Applied mathematics, 20(4):429-449, 1998. Google Scholar
  2. Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. A composition theorem for randomized query complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 10:1-10:13, 2017. Google Scholar
  3. Richard Beigel. The polynomial method in circuit complexity. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 82-95, 1993. URL: https://doi.org/10.1109/SCT.1993.336538.
  4. Shalev Ben-David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions: Extended abstract. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 240-246. IEEE, 2020. Google Scholar
  5. Shalev Ben-David and Robin Kothari. Randomized query complexity of sabotaged and composed functions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 60:1-60:14, 2016. Google Scholar
  6. Ethan Bernstein and Umesh V. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411-1473, 1997. URL: https://doi.org/10.1137/S0097539796300921.
  7. Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In 22nd Annual IEEE Conference on Computational Complexity (CCC), pages 24-32, 2007. URL: https://doi.org/10.1109/CCC.2007.18.
  8. Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC), pages 120-130, 2001. URL: https://doi.org/10.1109/CCC.2001.933879.
  9. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and markov-bernstein inequalities. Inf. Comput., 243:2-25, 2015. Earlier version in ICALP'13. URL: https://doi.org/10.1016/j.ic.2014.12.003.
  10. Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM J. Comput., 50(1):171-210, 2021. URL: https://doi.org/10.1137/19M1310153.
  11. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation theorems via pseudo-random properties. Comput. Complex., 28(4):617-659, 2019. URL: https://doi.org/10.1007/s00037-019-00190-7.
  12. Hong-Bin Chen and Frank K. Hwang. A survey on nonadaptive group testing algorithms through the angle of decoding. J. Comb. Optim., 15(1):49-59, 2008. URL: https://doi.org/10.1007/s10878-007-9083-3.
  13. Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 295-304. IEEE Computer Society, 2016. Google Scholar
  14. Arkadii Georgievich Dyachkov and Vladimir Vasil'evich Rykov. A survey of superimposed code theory. Problems of Control and Information Theory, 12(4):1-13, 1983. Google Scholar
  15. Peter Frankl and Norihide Tokushige. The Erdos-Ko-Rado theorem for integer sequences. Comb., 19(1):55-63, 1999. URL: https://doi.org/10.1007/s004930050045.
  16. Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput., 16:1-30, 2020. Google Scholar
  17. Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. A composition theorem for randomized query complexity via max-conflict complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, pages 64:1-64:13, 2019. Google Scholar
  18. Mika Göös and T. S. Jayram. A composition theorem for conical juntas. In 31st Conference on Computational Complexity (CCC), pages 5:1-5:16, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.5.
  19. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835-1869, 2016. Google Scholar
  20. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435-2450, 2018. URL: https://doi.org/10.1137/16M1059369.
  21. Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM J. Comput., 49(4), 2020. Earlier version in FOCS'17. URL: https://doi.org/10.1137/17M115339X.
  22. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR functions. SIAM J. Comput., 47(1):208-217, 2018. Earlier version in FOCS'16. URL: https://doi.org/10.1137/17M1136869.
  23. Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of linear sketching under modular updates. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 13:1-13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  24. Peter Høyer, Troy Lee, and Robert Spalek. Negative weights make adversaries stronger. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 526-535, 2007. Google Scholar
  25. Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. Linear sketching over f_2. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 8:1-8:37. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  26. Hartmut Klauck. On quantum and probabilistic communication: Las vegas and one-way protocols. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pages 644-651, 2000. URL: https://doi.org/10.1145/335305.335396.
  27. Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Log-rank and lifting for and-functions. In Proceedings of 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 197-208. ACM, 2021. URL: https://doi.org/10.1145/3406325.3450999.
  28. Srijita Kundu. One-way quantum communication complexity with inner product gadget. Electron. Colloquium Comput. Complex., 24:152, 2017. Comment #1 to TR17-152. Google Scholar
  29. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  30. Bruno Loff and Sagnik Mukhopadhyay. Lifting theorems for equality. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 126 of LIPIcs, pages 50:1-50:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  31. László Lovász and Michael E. Saks. Lattices, möbius functions and communication complexity. In 29th Annual Symposium on Foundations of Computer Science (FOCS), pages 81-90, 1988. URL: https://doi.org/10.1109/SFCS.1988.21924.
  32. Shachar Lovett. Communication is bounded by root of rank. J. ACM, 63(1):1:1-1:9, 2016. URL: https://doi.org/10.1145/2724704.
  33. Nikhil S. Mande, Suhail Sherif, and Swagato Sanyal. One-way communication complexity and non-adaptive decision trees. CoRR, abs/2105.01963, 2021. URL: http://arxiv.org/abs/2105.01963.
  34. Ashley Montanaro. Nonadaptive quantum query complexity. Inf. Process. Lett., 110(24):1110-1113, 2010. URL: https://doi.org/10.1016/j.ipl.2010.09.009.
  35. Ashley Montanaro. A composition theorem for decision tree complexity. Chicago J. Theor. Comput. Sci., 2014, 2014. Google Scholar
  36. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  37. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. URL: https://books.google.com/books?id=-s4DEy7o-a0C.
  38. Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Comb., 19(3):403-435, 1999. URL: https://doi.org/10.1007/s004930050062.
  39. Ben Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560-569, 2011. Google Scholar
  40. Swagato Sanyal. One-way communication and non-adaptive decision tree. Electron. Colloquium Comput. Complex., 24:152, 2017. URL: https://eccc.weizmann.ac.il/report/2017/152.
  41. Swagato Sanyal. Fourier sparsity and dimension. Theory of Computing, 15(11):1-13, 2019. URL: https://doi.org/10.4086/toc.2019.v015a011.
  42. Alexander A. Sherstov. Making polynomials robust to noise. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), pages 747-758, 2012. Google Scholar
  43. Alexander A. Sherstov. Approximating the AND-OR tree. Theory Comput., 9:653-663, 2013. URL: https://doi.org/10.4086/toc.2013.v009a020.
  44. Avishay Tal. Properties and applications of boolean function composition. In Innovations in Theoretical Computer Science (ITCS), pages 441-454, 2013. Google Scholar
  45. VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971. Google Scholar
  46. Ronald de Wolf. Quantum communication and complexity. Theoretical Computer Science, 287(1):337-353, 2002. URL: https://doi.org/10.1016/S0304-3975(02)00377-8.
  47. Hsin-Lung Wu. On the communication complexity of AND functions. IEEE Transactions on Information Theory, 2021. Google Scholar
  48. Xiaodi Wu, Penghui Yao, and Henry S. Yuen. Raz-mckenzie simulation with the inner product gadget. Electron. Colloquium Comput. Complex., 24:10, 2017. URL: https://eccc.weizmann.ac.il/report/2017/010.
  49. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing (STOC), pages 209-213, 1979. URL: https://doi.org/10.1145/800135.804414.
  50. Julius Žilinskas, Algirdas Lančinskas, and Mario R Guarracino. Pooled testing with replication as a mass testing strategy for the covid-19 pandemics. Scientific Reports, 11(1):1-7, 2021. 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