The hardness of decision tree complexity
Bruno Loff (University of Lisbon)
Abstract: In the world of formal languages, we have always been interested in the problem of finding the smallest “algorithm” for deciding a given language. Moore’s algorithm for DFA minimization is a standard part of a first course in theory of computing. Jiang and Ravikumar have shown, on the other hand, that NFA minimization is PSPACE-hard.
We will discuss a related problem for the computational model of deterministic decision trees. Let $f$ be a Boolean function given as either a truth table or as a circuit. In both of these cases, how difficult is it to find the smallest complexity of a decision tree for computing $f$? (This is commonly known as the “query complexity” of $f$). We will show that this problem is NC_1-hard and PSPACE-hard, respectively. The second bound is tight, and the first bound is close to being tight.
formal languages and automata theory
Audience: researchers in the topic
| Organizers: | Luca Prigioniero*, Rogério Reis* |
| *contact for this listing |