Randomized query complexity of sabotaged and composed functions

DOI10.4230/LIPICS.ICALP.2016.60MaRDI QIDQ4598199zbMATH OpenFDO

Authors Shalev Ben-David, Robin Kothari

Publication date 19 December 2017

zbMATH Keywords

composition theoremlifting theoremrandomized query complexitydecision-tree complexitypartition bound

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 6913819
• A composition theorem for randomized query complexity
• Query-to-communication lifting for BPP

Cited in

(9)

• A composition theorem for randomized query complexity
• Query-to-communication lifting for BPP
• All classical adversary methods are equivalent for total functions
• Low-sensitivity functions from unambiguous certificates
• Query-to-communication lifting using low-discrepancy gadgets
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• scientific article; zbMATH DE number 7561557 (Why is no real title available?)
• Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
• The Zero-Error Randomized Query Complexity of the Pointer Function

This page was built for publication: Randomized query complexity of sabotaged and composed functions

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