REVIEW 1 cited by
A Note on Amortized Branching Program Complexity
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
In this paper, 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 doubly exponential number of copies of $f$ which has linear size per copy of $f$. This result disproves a conjecture about non-uniform catalytic computation, rules out a certain type of bottleneck argument for proving non-monotone space lower bounds, and can be thought of as a constructive analogue of Razborov's result that submodular complexity measures have maximum value $O(n)$.
Forward citations
Cited by 1 Pith paper
-
Catalytic Computing and Register Programs Beyond Log-Depth
For every positive epsilon, circuits in SAC^2 can be evaluated with O(log^2 n / log log n) work space and near-polynomial catalytic memory, improving the previous free-space bound by a factor of log log n.
Discussion (0). Continue with ORCID to comment.