Exploring the average values of Boolean functions via asymptotics and experimentation

DOI10.1137/1.9781611972962.10MaRDI QIDQ5233153zbMATH OpenOpenAlexFDO

Authors Mark Daniel Ward, Robin Pemantle

Publication date 16 September 2019

Published in 2006 Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611972962.10

Mathematics Subject Classification ID

Combinatorial probability (60C05) Data structures (68P05) Combinatorics in computer science (68R05)

Recommendations

• A sprouting tree model for random boolean functions
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
• And/Or Trees Revisited
• The growing tree distribution on Boolean functions.
• On the average-case complexity of Boolean functions under binomial distribution on their domains

Cited in

(4)

• Boolean averaging in a statistical mechanics model and in an analog-to-digital converter
• Minimax functions on Galton-Watson trees
• The distance on the slightly supercritical random series-parallel graph
• Finite-depth scaling and an exact Bernoulli-leaf identity for the min-plus process on the binary tree

This page was built for publication: Exploring the average values of Boolean functions via asymptotics and experimentation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233153)