Document Open Access Logo

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Authors Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.28.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Shalev Ben-David
  • University of Waterloo, Canada
Mika Göös
  • Stanford University, CA, USA
Robin Kothari
  • Microsoft Quantum and Microsoft Research, Redmond, WA, USA
Thomas Watson
  • University of Memphis, TN, USA

Funding

  • Watson, Thomas: Supported by NSF grant CCF-1657377.

Acknowledgements

We thank Badih Ghazi for interesting discussions about this work, and we thank anonymous reviewers for their comments.

Cite AsGet BibTex

Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson. When Is Amplification Necessary for Composition in Randomized Query Complexity?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.28

Abstract

Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probability of the decision tree for g, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
Keywords
  • Amplification
  • composition
  • query complexity

Metrics

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

References

  1. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th Symposium on Theory of Computing (STOC), pages 863-876. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897644.
  2. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. Journal of the ACM, 64(5):32:1-32:24, 2017. URL: https://doi.org/10.1145/3106234.
  3. 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 Proceedings of the 37th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 10:1-10:13. Schloss Dagstuhl, 2017. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.10.
  4. Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, and Li-Yang Tan. The power of many samples in query complexity. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl, 2020. To appear. Google Scholar
  5. Shalev Ben-David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions. Technical Report 2002.10809, arXiv, 2020. URL: http://arxiv.org/abs/2002.10809.
  6. Shalev Ben-David and Robin Kothari. Randomized query complexity of sabotaged and composed functions. Theory of Computing, 14(1):1-27, 2018. URL: https://doi.org/10.4086/toc.2018.v014a005.
  7. Eric Blais and Joshua Brody. Optimal separation and strong direct sum for randomized query complexity. In Proceedings of the 34th Computational Complexity Conference (CCC), pages 29:1-29:17. Schloss Dagstuhl, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.29.
  8. Eric Blais, Joshua Brody, and Badih Ghazi. The information complexity of hamming distance. In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM), pages 465-489. Schloss Dagstuhl, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.465.
  9. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  10. Chris Cade. Post-selected classical query complexity. Technical report, arXiv, 2018. URL: http://arxiv.org/abs/1804.10010.
  11. Chinmoy Dutta and Jaikumar Radhakrishnan. Lower bounds for noisy wireless networks using sampling algorithms. In Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), pages 394-402. IEEE, 2008. URL: https://doi.org/10.1109/FOCS.2008.72.
  12. William Evans and Nicholas Pippenger. Average-case lower bounds for noisy Boolean decision trees. SIAM, 28(2):433-446, 1998. URL: https://doi.org/10.1137/S0097539796310102.
  13. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM Journal on Computing, 23(5):1001-1018, 1994. URL: https://doi.org/10.1137/S0097539791195877.
  14. Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. A composition theorem for randomized query complexity via max-conflict complexity. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 64:1-64:13. Schloss Dagstuhl, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.64.
  15. Dmitry Gavinsky and Shachar Lovett. En route to the log-rank conjecture: New reductions and equivalent formulations. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 514-524. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_43.
  16. Mika Göös and T. S. Jayram. A composition theorem for conical juntas. In Proceedings of the 31st Computational Complexity Conference (CCC), pages 5:1-5:16. Schloss Dagstuhl, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.5.
  17. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication vs. partition number. ACM Transactions on Computation Theory, 10(1):4:1-4:20, 2018. URL: https://doi.org/10.1145/3170711.
  18. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. URL: https://doi.org/10.1137/15M103145X.
  19. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM Journal on Computing, 47(6):2435-2450, 2018. URL: https://doi.org/10.1137/16M1059369.
  20. Navin Goyal and Michael Saks. Rounds vs. queries tradeoff in noisy computation. Theory of Computing, 6(1):113-134, 2010. URL: https://doi.org/10.4086/toc.2010.v006a006.
  21. Rahul Jain, Hartmut Klauck, and Miklos Santha. Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters, 110(20):893-897, 2010. URL: https://doi.org/10.1016/j.ipl.2010.07.020.
  22. Jedrzej Kaniewski, Troy Lee, and Ronald de Wolf. Query complexity in expectation. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 761-772. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_62.
  23. Claire Kenyon and Valerie King. On Boolean decision trees with faulty nodes. Random Structures and Algorithms, 5(3):453-464, 1994. URL: https://doi.org/10.1002/rsa.3240050306.
  24. Marco Molinaro, David Woodruff, and Grigory Yaroslavtsev. Beating the direct sum theorem in communication complexity with implications for sketching. In Proceedings of the 24th Symposium on Discrete Algorithms, pages 1738-1756. ACM-SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.125.
  25. Ilan Newman. Computing in fault tolerant broadcast networks and noisy decision trees. Random Structures and Algorithms, 34(4):478-501, 2009. URL: https://doi.org/10.1002/rsa.20240.
  26. Mert Saglam. Near log-convexity of measured heat in (discrete) time and consequences. In Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS), pages 967-978. IEEE, 2018. URL: https://doi.org/10.1109/FOCS.2018.00095.
  27. Alexander Sherstov. Making polynomials robust to noise. Theory of Computing, 9:593-615, 2013. URL: https://doi.org/10.4086/toc.2013.v009a018.
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