A Note on Amortized Space Complexity.
Aaron Henry Potechin · arXiv (Cornell University) · 2016
In this note, we show that while almost all functions require exponential size branching programs to compute, for all functions $f$ there is a branching program computing a large number of copies of $f$ which has linear size per copy of $f$. We then discuss which non-monotone lower bound approaches for branching programs are ruled out by this result.