一句话：实现了一个纯函数式库，用于计算布尔函数的 level-p 复杂度，并应用于两级迭代多数函数，改进了先前结果。
布尔函数的复杂度衡量评估它所需的输入位数，level-p 复杂度定义为输入独立同分布服从伯努利(p)时的最小期望成本。本文将该问题指定为在所有可能决策树中选取最小期望成本，并设计了一个纯函数式库来求解。库中使用 thinning 和记忆化提升效率，用类型类分离关注点，用多项式（集合）表示复杂度，并用多项式因式分解和求根实现 thinning 所需的序关系。最后，作者计算了两级迭代多数函数的 level-p 复杂度，并改进了 J. Jansson 的先前结果。
Abstract This paper describes a purely functional library for computing level- p -complexity of Boolean functions and applies it to two-level iterated majority. Boolean functions are simply functions from n bits to one bit, and they can describe digital circuits, voting systems, etc. An example of a Boolean function is majority, which returns the value that has majority among the n input bits for odd n . The complexity of a Boolean function f measures the cost of evaluating it: how many bits of the input are needed to be certain about the result of f . There are many competing complexity measures, but we focus on level- p -complexity — a function of the probability p that a bit is 1. The level- p -complexity $D_p(f)$ is the minimum expected cost when the input bits are independent and identically distributed with Bernoulli( p ) distribution. We specify the problem as choosing the minimum expected cost of all possible decision trees — which directly translates to a clearly correct, but very inefficient implementation. The library uses thinning and memoization for efficiency and type classes for separation of concerns. The complexity is represented using (sets of) polynomials, and the order relation used for thinning is implemented using polynomial factorization and root counting. Finally, we compute the complexity for two-level iterated majority and improve on an earlier result by J. Jansson.
@article{paperbot2152,
title = {Level-p-complexity of Boolean functions using thinning, memoization, and polynomials},
author = {JULIA JANSSON and PATRIK JANSSON},
journal = {Journal of Functional Programming},
volume = {33},
year = {2023},
doi = {10.1017/s0956796823000102}
}