scientific article; zbMATH DE number 6913819

DOI10.4086/TOC.2018.V014A005MaRDI QIDQ4577913zbMATH OpenOpenAlexFDO

Authors Shalev Ben-David, Robin Kothari

Publication date 6 August 2018

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1605.09071

zbMATH Keywords

randomized algorithmsquery complexitycomposition theorems

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

• Randomized query complexity of sabotaged and composed functions
• A composition theorem for randomized query complexity
• A composition theorem for randomized query complexity via max-conflict complexity
• On the complexity of functions for random access machines
• Randomized complexity
• scientific article; zbMATH DE number 7711600
• Towards better separation between deterministic and randomized query complexity
• Separation between deterministic and randomized query complexity
• scientific article; zbMATH DE number 1775407
• The Zero-Error Randomized Query Complexity of the Pointer Function

Cites work

• Amortized Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Composition limits and separating examples for some Boolean function complexity measures
• How to compress interactive communication
• Nearly optimal separations between communication (or query) complexity and partitions
• On fractional block sensitivity
• On general minimax theorems
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Properties and applications of Boolean function composition
• Quantum Query Complexity of State Conversion
• Randomized Boolean decision trees: Several remarks
• Randomized query complexity of sabotaged and composed functions
• Reflections for quantum query algorithms
• Separations in query complexity using cheat sheets
• Super-logarithmic depth lower bounds via the direct sum in communication complexity

Cited in

(8)

• A composition theorem for randomized query complexity
• Randomized query complexity of sabotaged and composed functions
• Conflict complexity is lower bounded by block sensitivity
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)
• Query-to-communication lifting for BPP
• Query-to-communication lifting using low-discrepancy gadgets
• The Zero-Error Randomized Query Complexity of the Pointer Function
• Optimal separation and strong direct sum for randomized query complexity

This page was built for publication:

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