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.
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Overview
Syllabus
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
-
Computational Complexity
-
A New Minimax Theorem for Randomized Algorithms
-
Towards Optimal Separations between Quantum and Randomized Query Complexities
-
Undergrad Complexity at CMU - Randomized Complexity- RP, coRP, and ZPP
-
Undergrad Complexity at CMU - Savitch's Theorem and NL
-
Undergrad Complexity at CMU - The Immerman-Szelepcsényi Theorem
