(2022) Small Hazard-Free 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 hazard-free complexity and (standard) circuit complexity of explicit functions. This raises the question: which classes of functions permit efficient hazard-free 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 hazard-free 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 hazard-free 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 |