Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>

An $n$-bit boolean function is resilient to coalitions of size $q$
if no fixed set of $q$ bits is likely to influence the value of the
function when the other $n-q$ bits are chosen uniformly at random,
even though the function is nearly balanced. We construct explicit
functions resilient to ... more >>>

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>