IMSc Webinar

On (Simple) Decision Tree Rank

Yogesh Dahiya

IMSc

Webinar; join at https://zoom.us/j/99018916192?pwd=Vnd3YW1RbisxNlVhZGN5RXYvMVZ5Zz09 The central problem in Boolean function complexity is to understand exactly what makes a function hard to compute in a particular computational model. The power and limitations of a computation model are understood in terms of intrinsic complexity measures of functions. In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and the size corresponds to storage space. The depth measure is the most well studied one and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure is also studied but to a lesser extent. A decision tree measure that has received very little attention is the minimal rank of the decision tree, first introduced by Ehrenfeucht and Haussler in 1989. This measure is not polynomially related to depth, and hence it can reveal additional information about the complexity of a function. For instance, from several viewpoints, the PARITY function on n bits is significantly harder than the AND function on n bits. But both of them have the same depth measure, n. However, rank does reflect this difference in hardness, with the rank of AND being 1 and the rank of PARITY being n. In this paper, we study this measure further. We obtain upper and lower bounds on rank in terms of (variants of) certificate complexity. We also obtain upper and lower bounds on the rank for composed functions in terms of the depth of the outer function and the rank of the inner function. We compute the rank exactly for several natural functions and use them to show that all the bounds we have obtained are tight. https://zoom.us/j/99018916192?pwd=Vnd3YW1RbisxNlVhZGN5RXYvMVZ5Zz09 Meeting ID: 990 1891 6192 Passcode: 422343