(2022) Small HazardFree Transducers.

Text (Extended ArXiv version)
submission_arXiv.pdf  Accepted Version Available under License Creative Commons Attribution. Download (816kB)  Preview 
Abstract
Ikenmeyer et al. (JACM'19) proved an unconditional exponential separation between the hazardfree complexity and (standard) circuit complexity of explicit functions. This raises the question: which classes of functions permit efficient hazardfree circuits? In this work, we prove that circuit implementations of transducers with small state space are such a class. 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 present a construction that transforms any function arising from a transducer into an efficient circuit of size O(n) computing the hazardfree extension of the function. More precisely, given a transducer with s states, receiving n input symbols encoded by l bits, and computing n output symbols encoded by m bits, the transducer has a hazardfree circuit of size m*n*2^O(s+l) and depth O(s*log(n) + l); in particular, if s, l, m are element of O(1), size and depth are asymptotically optimal. In light of the strong hardness results by Ikenmeyer et al. (JACM'19), we consider this a surprising result.
Item Type:  Conference or Workshop Item (A Paper) (Paper) 

Divisions:  Christoph Lenzen (CL) 
Conference:  ITCS Innovations in Theoretical Computer Science 
Depositing User:  Johannes Bund 
Date Deposited:  07 Dec 2021 11:10 
Last Modified:  07 Dec 2021 11:10 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3522 
Actions
Actions (login required)
View Item 