Randomized query complexity of sabotaged and composed functions

DOI10.4230/LIPICS.ICALP.2016.60zbMATH Open1388.68094MaRDI QIDQ4598199FDOQ4598199

Authors: Shalev Ben-David, Robin Kothari 

Publication date: 19 December 2017

Recommendations

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

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)

Cited In (9)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
• The Zero-Error Randomized Query Complexity of the Pointer Function
• A composition theorem for randomized query complexity

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)