Randomized versus Deterministic Decision Tree Size

Explore the relationship between randomized and deterministic decision tree size complexity in this lecture by Nikhil Mande from the University of Liverpool. Delve into a groundbreaking result that demonstrates the logarithm of deterministic decision tree size complexity for total Boolean functions is at most the fourth power of its randomized counterpart, with minor exceptions. Examine the implications of this finding, including its impact on AND-OR query complexity and the concept of Boolean function rank. Learn about the use of block number in obtaining the main result and understand how this research builds upon and extends classic work in the field of computational complexity theory.

Randomized versus Deterministic Decision Tree Size