scientific article; zbMATH DE number 6913819
DOI10.4086/TOC.2018.V014A005zbMATH Open1398.68186arXiv1605.09071OpenAlexW2963864626MaRDI QIDQ4577913FDOQ4577913
Authors: Shalev Ben-David, Robin Kothari 
Publication date: 6 August 2018
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.09071
Title of this publication is not available (Why is that?)
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
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cites Work
- On general minimax theorems
- Complexity measures and decision tree complexity: a survey.
- Quantum Query Complexity of State Conversion
- How to compress interactive communication
- Amortized Communication Complexity
- Reflections for quantum query algorithms
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Composition limits and separating examples for some Boolean function complexity measures
- Randomized Boolean decision trees: Several remarks
- Nearly optimal separations between communication (or query) complexity and partitions
- Properties and applications of Boolean function composition
- On fractional block sensitivity
- Separations in query complexity using cheat sheets
- Randomized query complexity of sabotaged and composed functions
Cited In (8)
- Randomized query complexity of sabotaged and composed functions
- Conflict complexity is lower bounded by block sensitivity
- Title not available (Why is that?)
- Query-to-communication lifting for BPP
- Query-to-communication lifting using low-discrepancy gadgets
- Optimal separation and strong direct sum for randomized query complexity
- The Zero-Error Randomized Query Complexity of the Pointer Function
- A composition theorem 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)
