Small Hazard-Free Transducers

Recently, an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions has been shown (STOC'18). This raises the question: which classes of functions permit efficient hazard-free circuits? Our main result is as follows.A transducer is a finite state machine that transcribes, symbol by symbol, an input string of length n into an output string of length n. We prove that any function arising from a transducer with s states, that is input symbols which are encoded by l bits, has a hazard-free circuit of size 2^{O(s+l)}*n and depth O(l+ s*log n); in particular, if s and  l are constants,  size and depth are asymptotically optimal. We utilize our main result to derive efficient circuits for k-recoverable addition. Informally speaking, a code is k-recoverable if it does not increase uncertainty regarding the encoded value, so long as it is guaranteed that it is from {x,x+1,...,x+k} for some natural number x. We provide an asymptotically optimal k-recoverable code. We also realize a transducer with O(k) states that adds two codewords from this k-recoverable code. Combined with our main result, we obtain a hazard-free adder circuit of size 2^{O(k)}n and depth O(k log n)  with respect to this code, i.e., a k-recoverable adder circuit that adds two codewords of n bits each. In other words, k-recoverable addition is fixed-parameter tractable with respect to k. We then reduce the maximum size of the state machines involved  to O(1),  resulting in a circuit for k-recoverable addition of size O(n+k log k)  and depth O(log n), e.g., if the uncertainties of each of the addends span  constant length interval then, there is an asymptotically optimal   adder that attains the best possible output uncertaint