The Power of Decision Trees for Composition and Search Problems

The unifying theme of this thesis are decision trees. Given a boolean function $f$ and an input $x$, a decision tree computes the value $f(x)$ by repeatedly querying bits of $x$. Our work is two-fold. On one hand, we investigate direct sums and other related problems in the context of query complexity; on the other hand, we focus on the power of decision trees as performing reductions between total $NP$-search problems.

A direct sum theorem states that the cost of computing $k$ instances of a function is at least $\Omega(k)$ times the resources spent computing a single instance. This theme has been intensively studied for many models of computation and is for instance known to hold for (randomised) decision trees (Brody and Blais CCC19). We initiate the study of this question for parity decision trees in chapter 1 and prove two such statements in the randomised case. We then work on a generalisation of the direct sum property where instead of returning the value of each instance (a vector of size $k$), we merely need to compute their value aggregated by some function $g$. In chapter 2, we introduce a new boolean function measure $LR$ and show that it satisfies an inner-optimal composition theorem for randomised query complexity: $R(g \circ f^k) \geq \Omega(R(g) \cdot LR(f))$ for all $f$ and $g$ (and $LR$ is the largest such measure). In chapter 3, we also show that in the special case $g = MAJ_k$, a super-multiplicative relationship holds: $R(MAJ_k \circ f^k) \geq \Omega(k \cdot bR_{1/k}(f))$ so that it is necessary to decrease the error probability of each copy to compute their majority.

In the second part of this thesis, we focus on $TFNP$ and its subclasses which have been at the heart of several recent breakthroughs. In chapter 4, we show that the collapse $CLS = PLS \cap PPAD$ (Fearnley et. al. JACM22) can actually be extended: $EOPL = PLS \cap PPAD$. By means of another black reduction, we also get $SOPL = PLS \cap PPADS$. In chapter 5, we study query analogues of $TFNP$; in particular, we show that $PLS^dt \not\subseteq PPP^dt$, thereby settling the last open relationship between the five original $TFNP$ classes (Beame et. al. JACM98 and Buresh-Oppenheim CCC04). To show this, we further develop the connection between total search problems and proof complexity; for instance, we prove that $PPADS^dt$ corresponds to the Sherali-Adams proof system with unary coefficients. Finally, in chapter 6, we rule out certain classes of reductions trying to base $TFNP$-hardness on secure one-way functions.