Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL DEGREE OF BOOLEAN FUNCTIONS:
Reports tagged with polynomial degree of Boolean functions:
TR22-135 | 18th September 2022
Rahul Chugh, Supartha Poddar, Swagato Sanyal

Decision Tree Complexity versus Block Sensitivity and Degree

Comments: 1

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>




ISSN 1433-8092 | Imprint