The power of many samples in query complexity

DOI10.4230/LIPICS.ICALP.2020.9MaRDI QIDQ6842571zbMATH OpenFDO

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

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.9

zbMATH Keywords

composition theoremsquery complexity

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A composition theorem for decision tree complexity
• A composition theorem for randomized query complexity
• A composition theorem for randomized query complexity via max-conflict complexity
• All classical adversary methods are equivalent for total functions
• Choosing, agreeing, and eliminating in communication complexity
• Complexity measures and decision tree complexity: a survey.
• Composition limits and separating examples for some Boolean function complexity measures
• CREW PRAM<scp>s</scp> and Decision Trees
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• On fractional block sensitivity
• Properties and applications of Boolean function composition
• Quantum certificate complexity
• Randomized communication versus partition number
• Randomized query complexity of sabotaged and composed functions
• Reflections for quantum query algorithms
• Towards proving strong direct product theorems

Cited in

(4)

• Randomized query composition and product distributions
• A new minimax theorem for randomized algorithms
• Quantum sabotage complexity
• Lifting to randomized parity decision trees

This page was built for publication: The power of many samples in query complexity

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