An Operator Approach to Register Programs for Catalytic Computing

1.1 Catalytic computation

• Catalytic computation asks whether a space-bounded machine can gain power from arbitrary auxiliary memory that it must completely restore; a seminal paper proves TC^1 is contained in Catalytic Logspace.Source: §1.1 · p. 2

1.2 Register programs

• Clean register programs restore every work register, and Buhrman et al. used them to simulate catalytic machines and compute powers with four input accesses [BCK`14].The open trade-off asks how polynomial degree depends on the number of registers and input calls.Source: §1.2 · p. 3

1.3 Our results

• Four input accesses are necessary for cleanly computing degree-at-least-three polynomials over characteristic-zero fields; with two passive-output registers, degree d requires at least d + 1 accesses.The paper also constructs x^(2r−1) with four accesses and r registers when the field has characteristic 0 or prime p > 2r−1.Source: §1.3 · p. 3

1.4 Organization

• The paper proceeds from operator preliminaries to lower bounds, then to a uniform four-call construction and applications to catalytic computation, streaming, and matrix powering.The construction cancels four transformations on work registers and inserts output updates to compute x^(2r−1).Source: §1.3 · pp. 3–4, §1.4 · p. 4

2.1 Catalytic computation

• A catalytic machine may modify an arbitrary initial tape string but must restore it exactly; the tape size is bounded by the natural addressing limit of 2O(s).The class CSPACE(s,c) captures workspace s and catalytic space c.Source: §2.1 · p. 4

2.2 Register programs

• A register program uses polynomial updates and input accesses; clean computation restores non-output registers, while passive outputs cannot be used as workspace.An input access becomes a recursive call when its input is another program’s output; clean programs can be simulated catalytically [BCK`14].Source: §2.2 · pp. 4–5

2.3 Operator representations

• The operator representation treats register instructions as linear maps on register polynomials and expresses their compositions using formal exponentials and commutator identities.The Campbell–Baker–Hausdorff identity is stated for the case where the commutator commutes with both operators.Source: §2.3 · p. 5

2.4 Single-access operator representations

• A locally nilpotent derivation has a finite exponential action on each polynomial; under triangular dependence conditions, its exponential is conjugate to a single-access translation.The translation of X by λx is represented by exp(λxB_X), where B_X is formal differentiation with respect to X.Source: §2.4 · p. 6

3.1 Product representation of passive programs

• A clean passive program with t input accesses is represented as a product of exponentials of locally nilpotent derivations, each commuting with the output derivative.This operator representation turns register restoration into an operator identity.Source: §3.1 · p. 7

3.2 Lower bounds for one, two, and three calls

• With at most two input accesses, passive programs compute only polynomials of degree at most one, and every linear polynomial is achievable with one access.The bound holds regardless of the number of registers.Source: §3.2 · pp. 8–9
• Three input accesses permit degree at most two, and this bound is attained for every register count r ≥ 2.Cook and Mertz’s interpolation program computes x^2 with two registers and three calls.Source: §3.2 · p. 9
• Every passive-output program computing a polynomial of degree at least three requires at least four input accesses, independently of its register count.Thus, for degrees greater than two, the four-access bound of Buhrman et al. is optimal [BCK`14].Source: §3.2 · p. 10

3.3 The two-register case

• With two registers, computing degree d ≥ 2 requires at least d + 1 calls; the exact maximum degree with t calls is t − 1, attained by Lagrange interpolation.The matching construction is the Lagrange-interpolation register program of Cook and Mertz.Source: §3.3 · pp. 10–11

4 A Four-Call Register Program for x2r−1

• For every r ≥ 2, a four-input-access program uses r registers to compute x^(2r−1), encoding the r−1 work registers in a monic polynomial and restoring them to their initial values.Source: §4 · p. 11

4.1 The Four Transformations and the Closed-Loop Construction

• Encoding work-register contents as coefficients of a monic polynomial lets four derivation transformations form a closed loop that restores those contents.The derivations satisfy Lemma 2.7’s conditions, so each transformation uses one input access.Source: §4 · p. 11, §4.1 · pp. 12–13

4.2 Polynomial Updates for the Output Register

• The output updates use a unique pair of polynomials whose rational coefficients can be constructed uniformly from binomial coefficients.The updates are chosen so their total increment is x^(2r−1).Source: §4.2 · pp. 13–14

4.3 The Final Four-Call Construction

• The completed construction is correct and clean, and it is valid over fields of characteristic 0 or greater than 2r−1.Correctness and cleanliness follow from Lemma 2.7, Lemma 4.2, and Lemma 4.3.Source: §4.3 · p. 14
• Composing the program for x^(2r−1) with itself computes x^((2r−1)^2) using 16 input accesses.The section notes that this composition illustrates how register programs can be combined.Source: §4.3 · p. 14

4.4 Generalizing to Matrices

• The construction represents A by coordinates in a matrix basis and encodes its work registers as coefficients of a monic polynomial.Source: §4.4 · pp. 15–16
• Each of the four transformations accesses the linear form ℓ_A(z), and each such access is implemented with one access to A.Source: §4.4 · p. 16
• A linear map from homogeneous polynomials to matrices converts the polynomial identity into A^N, and its linearity lets the map act separately on each call-free output update.Source: §4.4 · pp. 16–17
• Over characteristic zero or characteristic p > 2r−1, A^(2r−1) can be computed using four input accesses to A.The matrix output adds m² cells to the scalar work-register storage.Source: §4.4 · p. 17

5.1 Frequency Moments for Catalytic Streaming Algorithms

• The frequency-moment algorithm uses O_r(nD log(m + 1)) bits of catalytic memory and O_r(D log(m + 1) + log n + log D) bits of regular memory.These bounds apply to the stated construction for frequency moments of order D.Source: §5.1 · p. 19
• The frequency-moment construction slightly improves known space bounds and reduces passes from D + 1 to Oε(D^ε) for every ε > 0.The comparison is with known catalytic streaming algorithms, including Becker et al. [BCC`26].Source: §5.1 · p. 19

5.2 Matrix Powering

• For matrix powering, the recursive-call bound is Oε(N^ε), removing the logarithmic factor in Alekseev et al.’s Oε(N^ε log N) bound.The construction also reduces the number of registers and works directly over the smaller field Fp [AFM`25, Thm. 2].Source: §5.2 · pp. 19–20

6 Conclusion and Future Directions

• The operator representation proves lower bounds on input accesses for degree-d polynomials over fields of characteristic 0.The conclusion also notes that register programs are restricted to commutative rings.Source: §6 · p. 20
• The authors give a uniform family of register programs computing x^(2r−1) using only r registers over any field K of characteristic 0 or characteristic p > 2r−1.Source: §6 · p. 20
• Composing clean register programs yields programs for x^N with r + 1 registers and O(r) input accesses, improving bounds for frequency moments in catalytic streaming and matrix powering.The passage’s access-count expression is truncated after “Or”; the stated applications and register count are preserved here without supplying the missing expression.Source: §6 · p. 20
• The optimality of the powering family remains unknown, including whether additional input accesses can increase the maximum degree for passive-output programs.The conclusion poses this as an open question rather than a result.Source: §6 · p. 20
• The study covers commutative rings; operator-based or alternative methods for noncommutative programs may improve results relating NC and CL.The operator framework can also be adapted to many algebraic representations, with many derivation choices left to explore.Source: §6 · p. 20

Appendix A: proof of Lemma 4.3

• The proof sets N = 2a + 1.This establishes the parameterization used in the proof.Source: Appendix A · p. 24
• It defines a weight function for monomials in h, c2, …, ca.The supplied text gives the beginning of the definition but not its full expression.Source: Appendix A · p. 24
• The stated weights assign 1 to h and j to cj.In particular, the passage states wt(h) = 1 and wt(cj) = j.Source: Appendix A · p. 24

Reduction to a single polynomial

• In centered coordinates, A(h) = −3 and A(cj) = a, and the coefficient of x in the output increment is singled out for the reduction.The passages also state that every solution satisfies a further condition, but do not provide its expression.Source: Reduction to a single polynomial · p. 24
• The proof defines Wa by lowering each power of h by one from the corresponding monomials in Va.Wa is spanned by h^(N−1), the terms ci h^(N−i−1), and the terms cicj h^(N−i−j−1).Source: Reduction to a single polynomial · p. 24
• The derivations A and B act triangularly on the specified spaces, with nonzero diagonal entries when d ≥ 1, so both maps are invertible.This makes the preceding output-difference condition equivalent to H = BΨ = −AΦ, with Ψ = B^-1H and Φ = −A^-1H.Source: Reduction to a single polynomial · p. 24
• A coefficientwise integral of exponential operators defines the polynomial used in the reduction, and AΦ = −H and BΨ = H supply the output-difference identities.The passages specify that the integral is coefficientwise and that the resulting three output differences follow using these identities.Source: Reduction to a single polynomial · p. 25
• The target is to find polynomials H for which Kx(H) contains neither h nor any ci.This is the condition used to reduce the problem to a single polynomial.Source: Reduction to a single polynomial · p. 25

Quadratic terms

• A0 and B0 commute, and both decrease weight by one.The coefficients of A0 are independent of h, which supports the commutation stated in the passage.Source: Quadratic terms · p. 25
• The power-series expansion of k begins with a quadratic term proportional to (2z + w)(z + w), and factoring it gives a multiplier u with u(0, 0) = −1/12.Because the sum operator lowers weight, it is nilpotent on the finite space under consideration and therefore invertible.Source: Quadratic terms · pp. 25–26
• The quadratic terms vanish exactly when (A0 + B0)(A0 + 2B0)H^(2) = 0.Here H^(2) is the part of H containing two coefficients ci, and the quadratic part is computed using A0 and B0.Source: Quadratic terms · pp. 25–26
• The substitution J(v) = R(v − h/2) gives (A0 + B0)J(v) = 0, and the variables c2, …, ca can be recovered from h and the coefficients of J.Consequently, every polynomial has a unique expression in h and those J coefficients.Source: Quadratic terms · p. 26
• A polynomial lies in ker(A0 + B0) exactly when its expression in h and the J coefficients is independent of h.The passage states this is equivalent to being purely a polynomial in the coefficients of J(v).Source: Quadratic terms · p. 26
• A quadratic polynomial of weight 2a in ker(A0 + 2B0) is a multiple of L(0)^2, where L(v) = R(v − h).This follows from the analogous triangular argument for L and the stated action of A0 + 2B0 on L(v).Source: Quadratic terms · p. 27

• The coefficient of x^3 is used to determine the λ_p parameters.Source: Linear terms · p. 27
• The coefficients of x and x^2 cancel in the expansion.Source: Linear terms · p. 27
• Adding the two equations yields triangular equations for the linear-term constraints.Source: Linear terms · p. 28
• All terms containing exactly one coefficient c_i vanish because the two expressions cancel.Source: Linear terms · p. 29

• The final normalization parameter is chosen as γ = (-1)^a (2a + 1)!.Source: Constant term and normalization · p. 30
• The solution is unique: the quadratic equations determine H(2) up to γ and β, linear equations force β = 0 and determine H(1), and normalization determines γ.Source: Constant term and normalization · p. 30
• The construction expresses H using a polynomial number of binomial terms, establishing logspace uniformity.Source: Constant term and normalization · p. 30
• The logspace-uniform four-call program works over every field of characteristic p > 2r - 1.Its coefficients lie in Z[1/(2r - 1)!], so reduction modulo such primes preserves the restoration and correctness identities.Source: Constant term and normalization · p. 31