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 >>>

In the catalytic logspace ($CL$) model of (Buhrman et.~al.~STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This ... more >>>

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random ... more >>>