High Precision Multiplicative-Error Approximation of #SAC¹ Functions in Logspace Uniform AC¹Research Paper
Counting computations can produce integers whose binary expansions are much longer than their inputs. A short arithmetic circuit may repeatedly multiply values, making exact output expensive even when the circuit itself has a compact description. An approximation can have a short floating-point representation, but a small absolute error does not by itself…