Decision trees have applications throughout computer science. A natural approach for constructing a decision tree to approximate some function f is recursive: Use a splitting criterion to decide what variable to put at the root and then recurse on the left and right subtrees. We prove the existence of an efficient splitting criterion for which the resulting tree well-approximates f and apply it to solve problems in diverse areas such as property testing, explainable machine learning, and query strategies for priced information.

About the Speaker.

Joint work with Neha Gupta, Jane Lange, and Li-Yang Tan.

Zoom Participation. See announcement.