Abstract
An mcatalytic branching program (Girard, Koucký, McKenzie 2015) is a set of m distinct branching programs for f which are permitted to share internal (i.e. nonsource nonsink) nodes. While originally introduced as a nonuniform analogue to catalytic space, this also gives a natural notion of amortized nonuniform space complexity for f, namely the smallest value G/m for an mcatalytic branching program G for f (Potechin 2017).
Potechin (2017) showed that every function f has amortized size O(n), witnessed by an mcatalytic branching program where m = 2^(2ⁿ1). We recreate this result by defining a catalytic algorithm for evaluating polynomials using a large amount of space but O(n) time. This allows us to balance this with previously known algorithms which are efficient with respect to space at the cost of time (Cook, Mertz 2020, 2021). We show that for any ε ≥ 2n^(1), every function f has an mcatalytic branching program of size O_ε(mn), where m = 2^(2^(ε n)). We similarly recreate an improved result due to Robere and Zuiddam (2021), and show that for d ≤ n and ε ≥ 2d^(1), the same result holds for m = 2^binom(n, ≤ ε d) as long as f is a degreed polynomial over 𝔽₂. We also show that for certain classes of functions, m can be reduced to 2^(poly n) while still maintaining linear or quasilinear amortized size.
In the other direction, we bound the necessary length, and by extension the amortized size, of any permutation branching program for an arbitrary function between 3n and 4n4.
BibTeX  Entry
@InProceedings{cook_et_al:LIPIcs.CCC.2022.8,
author = {Cook, James and Mertz, Ian},
title = {{Trading Time and Space in Catalytic Branching Programs}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {8:18:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16570},
URN = {urn:nbn:de:0030drops165708},
doi = {10.4230/LIPIcs.CCC.2022.8},
annote = {Keywords: complexity theory, branching programs, amortized, space complexity, catalytic computation}
}
Keywords: 

complexity theory, branching programs, amortized, space complexity, catalytic computation 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 