The Glued-Trees Problem was first introduced in the context of quantum walk on graphs. It is an example of a problem that may be solved exponentially faster in the query model via quantum walk, as compared to randomized algorithms. It has since played an important role in other contexts as well. We tightly characterize the classical query complexity of the problem. Unlike the quantum case, the characterization involves a combinatorial analysis of a random sampling process. We leave open the possibility of an algebraic analysis.

Joint with with Rui Peng Liu.