The primary goal of this paper is to define and study the interactive information complexity of functions. Let $f(x,y)$ be a function, and suppose Alice is given $x$ and Bob is given $y$. Informally, the interactive information complexity $IC(f)$ of $f$ is the least amount of information Alice and Bob ... more >>>

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ... more >>>

An $m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of $m$ distinct branching programs for $f$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>>

The Tree Evaluation Problem ($TreeEval$) (Cook et al. 2009) is a central candidate for separating polynomial time ($P$) from logarithmic space ($L$) via composition. While space lower bounds of $\Omega(\log^2 n)$ are known for multiple restricted models, it was recently shown by Cook and Mertz (2020) that TreeEval can be ... more >>>