On query complexity measures and their relations for symmetric functions

DOI10.1007/978-3-031-52213-0_5MaRDI QIDQ6547823zbMATH OpenFDO

Authors Rajat Mittal, Sanjay S. Nair, Sunayana Patro

Publication date 31 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-52213-0_5

zbMATH Keywords

computational complexityquantum physicsquery complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68Wxx)

Cites work

• A note on quantum algorithms and the minimal degree of -error polynomials for symmetric functions
• Complexity measures and decision tree complexity: a survey.
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 7663120 (Why is no real title available?)
• On fractional block sensitivity
• On the degree of Boolean functions as real polynomials
• On the power of Ambainis lower bounds
• Properties and applications of Boolean function composition
• Quantum approximate counting, simplified
• Quantum lower bounds by quantum arguments
• Quantum Query Complexity of State Conversion
• Separations between combinatorial measures for transitive functions
• The need for structure in quantum speedups
• The quantum query complexity of approximating the median and related statistics

This page was built for publication: On query complexity measures and their relations for symmetric functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6547823)