Document Open Access Logo

The Power of Many Samples in Query Complexity

Authors Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.9.pdf
  • Filesize: 0.58 MB
  • 18 pages

Document Identifiers

Author Details

Andrew Bassilakis
  • Stanford University, CA, USA
Andrew Drucker
  • University of Chicago, IL, USA
Mika Göös
  • Stanford University, CA, USA
Lunjia Hu
  • Stanford University, CA, USA
Weiyun Ma
  • Stanford University, CA, USA
Li-Yang Tan
  • Stanford University, CA, USA

Funding

  • Hu, Lunjia: supported by NSF Award IIS-1908774 and a VMware fellowship.
  • Ma, Weiyun: supported by a Stanford Graduate Fellowship.
  • Tan, Li-Yang: supported by NSF grant CCF-1921795 and CAREER Award CCF-1942123.

Acknowledgements

We thank Shalev Ben-David for correspondence about their ongoing work [Ben-David and Blais, 2020; Ben-David and Blais, 2020]. AD thanks Mark Braverman for interesting discussions of related topics.

Cite AsGet BibTex

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, and Li-Yang Tan. The Power of Many Samples in Query Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.9

Abstract

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Probabilistic computation
Keywords
  • Query complexity
  • Composition theorems

Metrics

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

References

  1. Scott Aaronson. Quantum certificate complexity. Journal of Computer and System Sciences, 74(3):313-322, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.020.
  2. Andris Ambainis, Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. All classical adversary methods are equivalent for total functions. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS), volume 96, pages 8:1-8:14, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.8.
  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 Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 93, pages 10:1-10:13, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.10.
  4. Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz, and Enav Weinreb. Choosing, agreeing, and eliminating in communication complexity. Computational Complexity, 23:1-42, 2014. URL: https://doi.org/10.1007/s00037-013-0075-7.
  5. Shalev Ben-David and Eric Blais. A new minimax theorem for randomized algorithms. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.10802.
  6. Shalev Ben-David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.10809.
  7. Shalev Ben-David and Robin Kothari. Randomized query complexity of sabotaged and composed functions. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55, pages 60:1-60:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.60.
  8. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. Complexity and Logic. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  9. 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), volume 132, pages 64:1-64:13, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.64.
  10. Justin Gilmer, Michael Saks, and Srikanth Srinivasan. Composition limits and separating examples for some boolean function complexity measures. Combinatorica, 36(3):265-311, 2016. URL: https://doi.org/10.1007/s00493-014-3189-x.
  11. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication versus partition number. ACM Transactions on Computation Theory, 10(1), 2018. URL: https://doi.org/10.1145/3170711.
  12. Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the 39th Symposium on Theory of Computing (STOC), STOC ’07, page 526–535, 2007. URL: https://doi.org/10.1145/1250790.1250867.
  13. Raghav Kulkarni and Avishay Tal. On fractional block sensitivity. Chicago Journal of Theoretical Computer Science, 2016(8), 2016. URL: https://doi.org/10.4086/cjtcs.2016.008.
  14. Ashley Montanaro. A composition theorem for decision tree complexity. Chicago Journal of Theoretical Computer Science, 2014(6), 2014. URL: https://doi.org/10.4086/cjtcs.2014.006.
  15. Noam Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6):999-1007, 1991. URL: https://doi.org/10.1137/0220062.
  16. Ben Reichardt. Reflections for quantum query algorithms. In Proceedings of the 22nd Symposium on Discrete Algorithms (SODA), pages 560-569, 2011. Google Scholar
  17. Petr Savický. On determinism versus unambiquous nondeterminism for decision trees. Technical Report TR02-009, Electronic Colloquium on Computational Complexity (ECCC), 2002. URL: http://eccc.hpi-web.de/report/2002/009/.
  18. Ronen Shaltiel. Towards proving strong direct product theorems. Computational Complexity, 12(1/2):1-22, 2004. URL: https://doi.org/10.1007/s00037-003-0175-x.
  19. Avishay Tal. Properties and applications of boolean function composition. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS), pages 441-454, 2013. URL: https://doi.org/10.1145/2422436.2422485.
  20. Andrew Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Symposium on Foundations of Computer Science (SFCS 1977), pages 222-227, October 1977. URL: https://doi.org/10.1109/SFCS.1977.24.
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