A Composition Theorem for Randomized Query Complexity

DOI10.4230/LIPIcs.FSTTCS.2017.10zbMath1491.68082arXiv1706.00335OpenAlexW2963520412MaRDI QIDQ5136299

Troy Lee, Miklos Santha, Srijita Kundu, Priyanka Mukhopadhyay, Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Swagato Sanyal

Publication date: 25 November 2020

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

zbMATH Keywords

decision treeshardness amplificationquery complexityXOR lemmacomposition theoremquery algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11)

Related Items (3)

Unnamed Item ⋮ Conflict complexity is lower bounded by block sensitivity ⋮ Lifting Theorems for Equality

Cites Work

• Complexity measures and decision tree complexity: a survey.
• On rank vs. communication complexity
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• Properties and applications of boolean function composition
• Structure of Protocols for XOR Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Composition Theorem for Randomized Query Complexity