On the Complexity of Hazard-free Circuits
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12168
- Type
- D - Journal article
- DOI
-
10.1145/3320123
- Title of journal
- JOURNAL OF THE ACM
- Article number
- 25
- First page
- 1
- Volume
- 66
- Issue
- 4
- ISSN
- 1535-9921
- Open access status
- Compliant
- Month of publication
- August
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
5
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper was published at STOC 2018. The paper solves a problem from 1957 by Huffman on hazards in Boolean functions. This has already led to follow-up papers on transducer construction and sorting circuits in Bund et al. "Small hazard-free transducers" (arxiv:1811.12369, 2018) and "Optimal Metastability-Containing Sorting via Parallel Prefix Computation" (IEEE Transactions on Computers, 2020), and on hazard detection in Komrath "On the complexity of detecting hazards" (Information Processing Letters, 2020). The recent "Notes on Hazard-Free Circuits" (arxiv:2012.10976, 2020) is also based on our new proof technique.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -