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.


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

Consultation statistics

This page has been seen 180 times.
This article's PDF has been downloaded 193 times.