Document Open Access Logo

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Authors Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.64.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
Keywords
  • query complexity
  • lower bounds

Metrics

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

Abstract

For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g.
The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n).
The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

Cite As Get BibTex

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 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.64

Author Details

Dmitry Gavinsky
  • Institute of Mathematics, Czech Academy of Sciences, 115 67 Žitna 25, Praha 1, Czech Republic
Troy Lee
  • Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, Australia
Miklos Santha
  • CNRS, IRIF, Université de Paris, 75205 Paris, France
  • Centre for Quantum Technologies, National University of Singapore, Singapore 117543
  • MajuLab, UMI 3654, Singapore
Swagato Sanyal
  • Indian Institute of Technology Kharagpur, India

Funding

Part of this work was conducted while T.L. and S.S. were at the Nanyang Technological University and the Centre for Quantum Technologies, supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13. This work was additionally supported by the Singapore National Research Foundation, the Prime Minister’s Office, Singapore and the Ministry of Education, Singapore under the Research Centres of Excellence programme under research grant R 710-000-012-135. This research was supported in part by the QuantERA ERA-NET Cofund project QuantAlgo. D.G. is partially funded by the grant 19-27871X of GA ČR.

Acknowledgements

We thank Rahul Jain for useful discussions. We thank Srijita Kundu and Jevgēnijs Vihrovs for their helpful comments on the manuscript. We thank Yuval Filmus for suggesting to look at the min-max version of conflict complexity, which led to the development of max-conflict complexity. We thank the anonymous reviewers for their helpful comments.

References

  1. Scott Aaronson. Quantum certificate complexity. Journal of Computer and System Sciences, 74(3):313-322, 2008. 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 2017, December 11-15, 2017, Kanpur, India, pages 10:1-10:13, 2017. Google Scholar
  3. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to Compress Interactive Communication. SIAM J. Comput., 42(3):1327-1363, 2013. URL: http://dx.doi.org/10.1137/100811969.
  4. Shalev Ben-David and Robin Kothari. Randomized Query Complexity of Sabotaged and Composed Functions. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 60:1-60:14, 2016. Google Scholar
  5. Dmitry Gavinsky, Troy Lee, and Miklos Santha. On the randomised query complexity of composition. Technical report, arXiv, 2018. URL: http://arxiv.org/abs/1801.02226.
  6. Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. A composition theorem for randomized query complexity via max conflict complexity. CoRR, abs/1811.10752, 2018. URL: http://arxiv.org/abs/1811.10752.
  7. Justin Gilmer, Michael Saks, and Srikanth Srinivasan. Composition limits and separating examples for some Boolean function complexity measures. Combinatorica, 36(3):265-311, 2016. Google Scholar
  8. 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, San Diego, California, USA, June 11-13, 2007, pages 526-535, 2007. Google Scholar
  9. Yaqiao Li. Conflict complexity is lower bounded by block sensitivity. Technical report, arXiv, 2018. URL: http://arxiv.org/abs/1810.08873.
  10. Ashley Montanaro. A composition theorem for decision tree complexity. Chicago J. Theor. Comput. Sci., 2014, 2014. Google Scholar
  11. Ben Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 560-569, 2011. Google Scholar
  12. Swagato Sanyal. A composition theorem via conflict complexity. Technical report, arXiv, 2018. URL: http://arxiv.org/abs/1801.03285.
  13. Avishay Tal. Properties and applications of boolean function composition. In Innovations in Theoretical Computer Science, ITCS '13, pages 441-454, 2013. Google Scholar
  14. John von Neumann. Zur Theorie der Gessellschaftsspiele. Math. Ann., 100:295-320, 1928. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact