scientific article; zbMATH DE number 6913819

DOI10.4086/TOC.2018.V014A005zbMath1398.68186arXiv1605.09071OpenAlexW2963864626MaRDI QIDQ4577913

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: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

randomized algorithmsquery complexitycomposition theorems

Mathematics Subject Classification ID

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

Related Items (4)

Query-to-Communication Lifting for BPP ⋮ Unnamed Item ⋮ Conflict complexity is lower bounded by block sensitivity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal direct sum results for deterministic and randomized decision tree complexity
• On general minimax theorems
• Randomized Boolean decision trees: Several remarks
• Composition limits and separating examples for some Boolean function complexity measures
• Complexity measures and decision tree complexity: a survey.
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• How to Compress Interactive Communication
• Properties and applications of boolean function composition
• Amortized Communication Complexity
• Separations in query complexity using cheat sheets
• Quantum Query Complexity of State Conversion

This page was built for publication: