Level-p-complexity of Boolean Functions: Using thinning, memoization, and polynomials
Channel: Patrik Jansson
Date: 2022-12-14

(joint work with Julia Jansson)
This talk presents a function for computing level-$p$-complexity of Boolean functions, and applies it to two-level iterated majority. The function is specified as a classical optimisation problem: first generate all candidates, then pick the best one. To make this function efficient we we use use thinning and memoization and for seperation of concerns we use type classes. The complexity is represented using polynomials, and the order relation used for thinning is implemented using polynomial factorisation and root-counting.
https://patrikja.owlstown.net/
There is now a preprint on arXiv: https://arxiv.org/abs/2302.02473 and associated Haskell code on GitHub: https://github.com/juliajansson/BoFunComplexity/