On the Complexity of Hazard-Free Formulas
ACM Transactions on Computation Theory · 30.06.2026 · 18 (2) · 1-38
DOI: 10.1145/3811821 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, online erschienen am 17.06.2026. Verfasst von Leah London Arazi und 1 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Israel Science Foundation, Blavatnik Family Foundation, European Research Council.
Abstract (Originalsprache)
This article studies the hazard-free formula complexity of Boolean functions. Hazard-free formulas are De Morgan formulas that may take input variables with an unknown value, but produce a Boolean output whenever it can be determined by the known bits. Our first result concerns the hazard-derivative approach of Ikenmeyer et al. (J. ACM, 2019) for proving lower bounds in the hazard-free model. We show that this approach yields optimal bounds only for unate functions, i.e., the monotone formula complexity of a hazard-derivative equals the hazard-free formula complexity of the function itself. Our second result proves that the hazard-free formula complexity of a uniformly random Boolean function is at most \(2^{(1+o(1))n}\) . Previously, no better upper bound than \(O(3^n)\) was known. Notably, unlike in the general Boolean case, where the typical formula complexity is derived from that of the multiplexer function with n -bit selector, the hazard-free formula complexity of a random function is smaller than the optimal hazard-free formula for the multiplexer by an exponential factor in n . We provide two proofs of this fact. The first is direct, bounding the number of prime implicants of a random Boolean function and constructing a DNF of the claimed size. The second introduces a new and independently interesting result: a weak converse to the hazard-derivative lower bound method, which gives an upper bound on the hazard-free complexity of a function in terms of the monotone complexity of a subset of its hazard-derivatives. Additionally, we explore the hazard-free formula complexity of block composition and obtain a hazard-free analogue of the result of Karchmer, Raz, and Wigderson (Computational Complexity, 1995) in the monotone setting. Our result implies a stronger lower bound on the hazard-free formula depth of the block composition of the set covering function with the multiplexer function than the bound obtained via the hazard-derivative method.
Förderung
- Israel Science Foundation
- Blavatnik Family Foundation
- European Research Council
Zitieren
APA
Arazi, L. L., & Shpilka, A. (2026). On the Complexity of Hazard-Free Formulas. ACM Transactions on Computation Theory, 18(2), 1-38. https://doi.org/10.1145/3811821
Vancouver
Arazi LL, Shpilka A. On the Complexity of Hazard-Free Formulas. ACM Transactions on Computation Theory. 2026;18(2):1-38. doi:10.1145/3811821
BibTeX
@article{Arazi2026,
author = {Arazi, Leah London and Shpilka, Amir},
title = {On the Complexity of Hazard-Free Formulas},
journal = {ACM Transactions on Computation Theory},
year = {2026},
volume = {18},
number = {2},
pages = {1--38},
doi = {10.1145/3811821}
}
EUVIMED