Document Open Access Logo

Certificate Games

Authors Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.32.pdf
  • Filesize: 0.81 MB
  • 24 pages

Document Identifiers

Author Details

Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Anna Gál
  • University of Texas at Austin, TX, USA
Sophie Laplante
  • Université Paris Cité, IRIF, France
Rajat Mittal
  • IIT Kanpur, India
Anupa Sunny
  • Université Paris Cité, IRIF, France

Funding

AS has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 754362. Additional support comes from the French ANR projects ANR-18-CE47-0010 (QUDATA) and ANR-21-CE48-0023 (FLITTLA) and the QOPT project funded by the European Union’s Horizon 2020 Research and Innovation Programme under Grant Agreement no. 731473 and 101017733.

Acknowledgements

We thank Jérémie Roland for helpful discussions, Chandrima Kayal for pointing out a function which separates 𝖢 and 𝖰, and the anonymous referees for helpful comments.

Cite As Get BibTex

Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny. Certificate Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.32

Abstract

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index i such that x_i≠ y_i, in a zero-communication setting. 
We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations. We show that complexity in the public coin model is upper bounded by Randomized query and Certificate complexity. On the other hand, it is lower bounded by fractional and randomized certificate complexity, making it a good candidate to prove strong lower bounds on randomized query complexity. Complexity in the private coin model is bounded from below by zero-error randomized query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. Whereas the public coin certificate game complexity is bounded from above by randomized query complexity, the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of n on the quantum certificate game complexity of the OR function, whose quantum query complexity is Θ(√n), then go on to show that this "non-signaling bottleneck" applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity. 
We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to λ², where λ is the spectral sensitivity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Circuit complexity
  • Theory of computation → Quantum query complexity
Keywords
  • block sensitivity
  • boolean function complexity
  • certificate complexity
  • query complexity
  • sensitivity
  • zero-communication two-player games

Metrics

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

Related Versions

References

  1. Scott Aaronson. Lower bounds for local search by quantum arguments. SIAM Journal on Computing, 35(4):804-824, 2006. URL: https://doi.org/10.1137/S0097539704447237.
  2. Scott Aaronson. Quantum certificate complexity. J. Comput. Syst. Sci., 74:313-322, 2008. Google Scholar
  3. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 863-876, 2016. URL: https://doi.org/10.1145/2897518.2897644.
  4. Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. In Symposium on Theory of Computing (STOC), pages 1330-1342. ACM, 2021. Google Scholar
  5. Andris Ambainis. Quantum lower bounds by quantum arguments. In Symposium on Theory of Computing (STOC), pages 636-643, 2000. URL: https://doi.org/10.1145/335305.335394.
  6. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. J. ACM, 64(5), September 2017. URL: https://doi.org/10.1145/3106234.
  7. Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1-8:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.8.
  8. Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021), volume 200, pages 30:1-30:39, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.30.
  9. Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari. Unambiguous DNFs and Alon-Saks-Seymour. In Symposium on Foundations of Computer Science, FOCS, 2021. Google Scholar
  10. Nikhil Bansal and Makrand Sinha. K-forrelation optimally separates quantum and classical query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1303-1316, 2021. Google Scholar
  11. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. Google Scholar
  12. 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, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00031.
  13. Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-Sensitivity Functions from Unambiguous Certificates. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of LIPIcs, pages 28:1-28:23, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.28.
  14. Shalev Ben-David and Robin Kothari. Randomized query complexity of sabotaged and composed functions. Theory of Computing, 14(5):1-27, 2018. URL: https://doi.org/10.4086/toc.2018.v014a005.
  15. Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5):493-505, 1998. URL: https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
  16. Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. Bell nonlocality. Rev. Mod. Phys., 86:419-478, April 2014. URL: https://doi.org/10.1103/RevModPhys.86.419.
  17. Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf. Nonlocality and communication complexity. Rev. Mod. Phys., 82:665-698, March 2010. URL: https://doi.org/10.1103/RevModPhys.82.665.
  18. Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny. Certificate games. CoRR, 2022. ECCC report TR-143 (2022). URL: http://arxiv.org/abs/2211.03396.
  19. R. Cleve, P. Høyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proc. of the 19th Annual IEEE Conference on Computational Complexity, pages 236-249, 2004. Google Scholar
  20. D. J. Foulis and C. H. Randall. Empirical logic and tensor products. In Interpretations and Foundations of Quantum Theory, volume Interpretations and Foundations of Quantum Theory, pages 1-20, 1981. Google Scholar
  21. 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.
  22. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212-219, 1996. Google Scholar
  23. Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949-955, 2019. URL: https://www.jstor.org/stable/10.4007/annals.2019.190.3.6.
  24. Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, and Jevgundefinednijs Vihrovs. Quadratically tight relations for randomized query complexity. Theor. Comp. Sys., 64(1):101-119, January 2020. URL: https://doi.org/10.1007/s00224-019-09935-x.
  25. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3:255-265, January 1990. Google Scholar
  26. V. M. Khrapchenko. Complexity of the realization of a linear function in the class of π-circuits. Mathematical notes of the Academy of Sciences of the USSR, 9:21-23, 1971. Google Scholar
  27. M. Kläy, C. H. Randall, and D. J. Foulis. Tensor products and probability weights. Int. J. Theor. Phys., 26(3):199-219, 1987. Google Scholar
  28. Elias Koutsoupias. Improvements on Khrapchenko’s theorem. Theor. Comput. Sci., 116(2):399-403, 1993. Google Scholar
  29. Raghav Kulkarni and Avishay Tal. On fractional block sensitivity. Chicago Journal of Theoretical Computer Science, 2016:1-16, 2016. Article 08. Google Scholar
  30. Sophie Laplante and Frédéric Magniez. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. SIAM Journal on Computing, 38(1):46-62, 2008. URL: https://doi.org/10.1137/050639090.
  31. Gatis Midrijanis. Exact quantum query complexity for total Boolean functions. CoRR, 2004. URL: http://arxiv.org/abs/quant-ph/0403168.
  32. Rajat Mittal, Sanjay S Nair, and Sunayana Patro. Lower bounds on quantum query complexity for symmetric functions. CoRR, 2021. URL: http://arxiv.org/abs/2110.12616.
  33. Noam Nisan. CREW PRAMS and decision trees. In Symposium on Theory of Computing, STOC '89, pages 327-335, 1989. URL: https://doi.org/10.1145/73007.73038.
  34. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. URL: https://doi.org/10.1007/BF01263419.
  35. Carlos Palazuelos and Thomas Vidick. Survey on nonlocal games and operator space theory. Journal of Mathematical Physics, 57, December 2015. Google Scholar
  36. Stefano Pironio. Lifting Bell inequalities. J. Math. Phys., 46:062112, 2005. Google Scholar
  37. C. H. Randall and D. J. Foulis. Operational statistics and tensor products. In Interpretations and Foundations of Quantum Theory, pages 21-28, 1981. Google Scholar
  38. Robert Špalek and Mario Szegedy. All quantum adversary methods are equivalent. Theory of Computing, 2(1):1-18, 2006. URL: https://doi.org/10.4086/toc.2006.v002a001.
  39. Avishay Tal. Properties and applications of boolean function composition. In Innovations in Theoretical Computer Science, ITCS '13, pages 441-454, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2422436.2422485.
  40. Uzi Vishkin and Avi Wigderson. Trade-offs between depth and width in parallel computation. SIAM J. Discrete Math., 14:303-314, 1985. Google Scholar
  41. Alexander Wilce. Tensor products in generalized measure theory. Int. J. Theor. Phys., 31(11):1915-1928, 1992. Google Scholar
  42. Alex Yu. Boolean function complexity measures. https://funcplot.com/table/, 2019. Adapted from [ABK16].
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