We are happy to report that the paper "Level-p-complexity of Boolean functions using thinning, memoization, and polynomials" has now appeared in the Journal of Functional Programming: doi:10.1017/S0956796823000102 with source code on github:juliajansson/BoFunComplexity. More about the background has been explained in earlier posts: 2023-08, 2023-03, and 2022-12.
The paper (and the code) is fully open access and we'd be happy to hear your ideas for follow-up work connected to the paper.
The technical meat of the paper is the specification and efficient implementation of the concept of "Level-p-complexity" for a Boolean function. The specification is itself executable (basically "generate all candidates, pick the least expensive") but with doubly exponential complexity. For the running example the set of candidates to sift through would be on the order of 10^100, thus completely intractable. The implementation combines a few algorithmic techniques:
- thinning: push as much as possible of "pick the least" into the recursive computation of the set of candidates
- memoization: save and reuse computation results for "subfunctions"
- polynomials: represent the polynomials symbolically, and compute exact root counts (used to figure out if one polynomial crosses another and thus neither is uniformly better).
The result is a computation which for the running example (the level-p-complexity of two-level iterated majority) finishes within seconds on a regular laptop.
Video recording of the ICFP 2024 presentation: https://www.youtube.com/watch?v=mxDjPTDwbGE