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 expressionsArticle

Authors: Antoine Genitrini 1; 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: Analytic combinatorics.,Probability distribution,Boolean functions,Implicational expressions,Complexity,Limiting ratio,Galton-Watson trees,[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]

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 164 times.
This article's PDF has been downloaded 185 times.