Overview
Explore a rigorous analysis of randomized query complexity in partial functions through this 23-minute IEEE conference talk. Delve into the intricacies of a tight composition theorem presented by Shalev Ben-David and Eric Blais from the University of Waterloo. Gain insights into advanced concepts in computational complexity theory and understand their implications for algorithm design and analysis.
Syllabus
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Taught by
IEEE FOCS: Foundations of Computer Science