Antoine Genitrini ; Bernhard Gittenberger - No Shannon effect on probability distributions on Boolean functions induced by random expressions

dmtcs:2784 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2784
No Shannon effect on probability distributions on Boolean functions induced by random expressionsConference paper

Authors: Antoine Genitrini ORCID1; Bernhard Gittenberger 2

  • 1 Parallélisme, Réseaux, Systèmes, Modélisation
  • 2 Institut für Diskrete Mathematik und Geometrie [Wien]


The Shannon effect states that "almost all'' Boolean functions have a complexity close to the maximal possible for the uniform probability distribution. In this paper we use some probability distributions on functions, induced by random expressions, and prove that this model does not exhibit the Shannon effect.

https://doi.org/10.46298/dmtcs.2784
Source: HAL:hal-01185582v1
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [en] Boolean functions, Implicational expressions, Complexity, Limiting ratio, Galton-Watson trees, Probability distribution, Analytic combinatorics.

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 341 times.
This article's PDF has been downloaded 360 times.