cispa_all_3522.pdf (797.07 kB)

# Small Hazard-Free Transducers

conference contribution

posted on 2023-11-29, 18:19 authored by Johannes Bund, Christoph LenzenChristoph Lenzen, Moti MedinaIkenmeyer 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.

## History

## Preferred Citation

Johannes Bund, Christoph Lenzen and Moti Medina. Small Hazard-Free Transducers. In: Innovations in Theoretical Computer Science (ITCS). 2022.## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

Innovations in Theoretical Computer Science (ITCS)## Legacy Posted Date

2021-12-07## Open Access Type

- Green

## BibTeX

@inproceedings{cispa_all_3522, title = "Small Hazard-Free Transducers", author = "Bund, Johannes and Lenzen, Christoph and Medina, Moti", booktitle="{Innovations in Theoretical Computer Science (ITCS)}", year="2022", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC