Document Open Access Logo

Fractional Certificates for Bounded Functions

Authors Shachar Lovett , Jiapeng Zhang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.84.pdf
  • Filesize: 0.67 MB
  • 13 pages

Document Identifiers

Author Details

Shachar Lovett
  • Department of Computer Science and Engineering, University of California San Diego, CA, USA
Jiapeng Zhang
  • Department of Computer Science, University of Southern California, Los Angeles, CA, USA

Funding

  • Lovett, Shachar: Research supported by NSF awards DMS 1953928 and CCF 2006443.
  • Zhang, Jiapeng: Research supported by NSF CAREER award 2141536.

Cite AsGet BibTex

Shachar Lovett and Jiapeng Zhang. Fractional Certificates for Bounded Functions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 84:1-84:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.84

Abstract

A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold more generally for any bounded function computed by a low degree polynomial. In this work we prove two new results towards establishing this conjecture: first, that any such polynomial has a small fractional certificate complexity; and second, that many inputs have a small sensitive block. We show that these would imply the Aaronson and Ambainis conjecture, assuming a conjectured extension of Talagrand’s concentration inequality. On the technical side, many classical techniques used in the analysis of Boolean functions seem to fail when applied to bounded functions. Here, we develop a new technique, based on a mix of combinatorics, analysis and geometry, and which in part extends a recent technique of Knop et al. (STOC 2021) to bounded functions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Mathematics of computing → Discrete mathematics
Keywords
  • Aaronson-Ambainis conjecture
  • fractional block sensitivity
  • Talagrand inequality

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. Google Scholar
  2. Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133-166, 2014. Google Scholar
  3. Andris Ambainis, Krišjānis Prūsis, and Jevgenijs Vihrovs. On block sensitivity and fractional block sensitivity. Lobachevskii Journal of Mathematics, 39(7):967-969, 2018. Google Scholar
  4. Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On query-to-communication lifting for adversary bounds. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.03415.
  5. Arturs Backurs and Mohammad Bavarian. On the sum of L₁ influences. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 132-143. IEEE, 2014. Google Scholar
  6. Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms. arXiv preprint, 2022. URL: http://arxiv.org/abs/2203.00212.
  7. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778-797, 2001. Google Scholar
  8. Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O'Donnell. On the Fourier tails of bounded functions over the discrete cube. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 437-446, 2006. Google Scholar
  9. Yuval Filmus, Hamed Hatami, Nathan Keller, and Noam Lifshitz. On the sum of the L₁ influences of bounded functions. Israel Journal of Mathematics, 214(1):167-192, 2016. Google Scholar
  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. Google Scholar
  11. Nathan Keller and Ohad Klein. Quantum speedups need structure. arXiv preprint, 2019. Paper was withdrawn because it contained an error. URL: http://arxiv.org/abs/1911.03748.
  12. Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Log-rank and lifting for AND-functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 197-208, 2021. Google Scholar
  13. Raghav Kulkarni and Avishay Tal. On fractional block sensitivity. Chicago J. Theor. Comput. Sci, 8:1-16, 2016. Google Scholar
  14. L Lovász. 2-matchings and 2-covers of hypergraphs. Acta Mathematica Hungarica, 26(3-4):433-444, 1975. Google Scholar
  15. Gatis Midrijanis. On randomized and quantum query complexities. arXiv preprint, 2005. URL: http://arxiv.org/abs/quant-ph/0501142.
  16. Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12):122206, 2012. Google Scholar
  17. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational complexity, 4(4):301-313, 1994. Google Scholar
  18. Ryan O'Donnell, Michael Saks, Oded Schramm, and Rocco A Servedio. Every decision tree has an influential variable. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 31-39. IEEE, 2005. Google Scholar
  19. Avishay Tal. Properties and applications of Boolean function composition. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 441-454, 2013. Google Scholar
  20. Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques, 81(1):73-205, 1995. 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 Imprint Privacy Contact