All reports by Author James Cook:

__
TR21-054
| 14th April 2021
__

James Cook, Ian Mertz#### Encodings and the Tree Evaluation Problem

__
TR20-056
| 17th April 2020
__

James Cook, Ian Mertz#### Catalytic Approaches to the Tree Evaluation Problem

__
TR12-175
| 13th December 2012
__

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan#### On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

James Cook, Ian Mertz

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

more >>>James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>>

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>