EUVIMEDEUVIMED entdecken
Crossref

A Study of Distributional Complexity Measures for Boolean Functions

Laurin Köhler-Schindler, Jeffrey E. Steif

ACM Transactions on Computation Theory · 19.05.2026

DOI: 10.1145/3814613 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, online erschienen am 19.05.2026. Verfasst von Laurin Köhler-Schindler und 1 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A number of complexity measures for Boolean functions have previously been introduced. These include (1) sensitivity, (2) block sensitivity, (3) witness complexity, (4) subcube partition complexity and (5) algorithmic complexity. Each of these is concerned with “worst-case” inputs. It has been shown that there is “asymptotic separation” between these complexity measures and very recently, due to the work of Huang, it has been established that they are all “polynomially related”. In this paper, we study the notion of distributional complexity where the input bits are independent and one considers all of the above notions in expectation. We obtain a number of results concerning distributional complexity measures, among others addressing the above concepts of “asymptotic separation” and being “polynomially related” in this context. We introduce a new distributional complexity measure, local witness complexity, which only makes sense in the distributional context and we also study a new version of algorithmic complexity which involves partial information. Many interesting examples are presented including some related to percolation. The latter connects a number of the recent developments in percolation theory over the last two decades with the study of complexity measures in theoretical computer science.

Zitieren

APA

Köhler-Schindler, L., & Steif, J. E. (2026). A Study of Distributional Complexity Measures for Boolean Functions. ACM Transactions on Computation Theory. https://doi.org/10.1145/3814613

Vancouver

Köhler-Schindler L, Steif JE. A Study of Distributional Complexity Measures for Boolean Functions. ACM Transactions on Computation Theory. 2026. doi:10.1145/3814613

BibTeX
@article{KhlerSchindler2026,
  author = {Köhler-Schindler, Laurin and Steif, Jeffrey E.},
  title = {A Study of Distributional Complexity Measures for Boolean Functions},
  journal = {ACM Transactions on Computation Theory},
  year = {2026},
  doi = {10.1145/3814613}
}
Kostenlos starten →