The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings, and each leaf is assigned an $\ell$-bit string.
The desired output is the value of the root, ... more >>>

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known ... more >>>

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspace-complete problem of computing the product of $k$ $n$-by-$n$ Boolean matrices with at most a single $1$ in each row and column. For all $d \le \log k$, this problem is solvable by $n^{O(dk^{1/d})}$ size monotone formulas of two ... more >>>