EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the Complexity of Hazard-Free Formulas

Leah London Arazi, Amir Shpilka

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →