Decision Tree Complexity versus Block Sensitivity and Degree

Rahul Chugh, Supartha Podder, Swagato Sanyal

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. It is known t…