Limiting Boolean Functions of Random And–Or Trees

Definitions and mathematical statement

An and--or expression tree is interpreted recursively: each leaf carries a Boolean input expression, and each internal vertex carries either conjunction $\wedge$ or disjunction $\vee$, applied to the expressions computed by its children. The source does not specify the admissible trees, their rooting or arities, the leaf expressions, the set of variables, or the full joint law of the labels. These choices are necessary to define the random Boolean functions precisely.

The following gives a conditional formulation when a fixed finite variable set is intended; this restriction is not supplied by the source. Fix $k\geq 1$, let $X_k=\{0,1\}^k$, and let $\mathcal B_k=\{f:X_k\to\{0,1\}\}$. Suppose $(T_n)_{n\geq1}$ are random finite rooted expression trees, with specified leaf expressions on $X_k$, specified admissible internal arities, and a specified joint labeling law implementing the source's phrase "uniformly random AND/OR labels." Let $F_n\in\mathcal B_k$ be the function obtained by recursive evaluation, and put $\mu_n(f)=\Pr(F_n=f)$.

Source question, conditional on those specifications. Determine hypotheses on the tree sequence and labeling model under which there exists a probability measure $\mu$ on $\mathcal B_k$ such that \[ \lim_{n\to\infty}\Pr(F_n=f)=\mu(\{f\})\qquad\text{for every }f\in\mathcal B_k. \] This is convergence in distribution on the finite discrete space $\mathcal B_k$. When a limit exists, determine when it is degenerate and characterize it in the nondegenerate regimes.

The intended meaning of "degenerate" remains unresolved. A point-mass limit means $\mu(\{f_0\})=1$ for some $f_0\in\mathcal B_k$. Concentration on constant functions instead means $\mu(\{\mathbf 0,\mathbf 1\})=1$, where $\mathbf 0(x)=0$ and $\mathbf 1(x)=1$ for every $x\in X_k$. These are different conditions, and the supplied record does not identify which is intended. If the variable set varies with $n$ or is infinite, a common function space and a topology or other precise convergence notion must also be supplied. The record therefore specifies a research question but does not determine a unique fully quantified conjecture.

Short English statement

The problem asks when Boolean functions computed by randomly labeled and--or trees have a limiting distribution, when that limit is degenerate, and how nondegenerate limits behave. A precise formulation requires the tree model, leaf labels, variable set, labeling law, and meaning of degeneracy. The fixed finite variable formulation above is conditional. The supplied status is partially solved, subject to the dated source qualifications.

Sources

• Supplied local registry record: permanent UnsolvedMath ID $30002721$, title "Limiting Boolean Functions of Random And--Or Trees," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. Local registry locations specified by the project are data/unsolvedmath/problems.json and catalog/problems.json; this draft uses the supplied record. No individual proposer is identified; the proposed year is recorded as 2014.
• Supplied source citation: Probability, Trees and Algorithms (2015), Oberwolfach Reports, pp. 2825--2871, DOI 10.4171/owr/2014/50. https://doi.org/10.4171/owr/2014/50. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference labeled "Broutin--Mailler, local limits": https://doi.org/10.1002/rsa.20758.
• Supplied literature reference labeled "And-or trees preprint": https://arxiv.org/abs/1510.06691.
• Supplied literature reference labeled "Oberwolfach report": https://doi.org/10.4171/owr/2014/50.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem partially solved and reports that general convergence and degenerate versus nondegenerate regimes are proved under explicit local-limit and end hypotheses, while no theorem covers every arbitrary random-tree sequence. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. The record expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports a manual semantic, typographic, and LaTeX review of its cleanup. These are supplied provenance claims, not independent verification of this draft or of the mathematical formulation.