# Level-\(p\)-complexity of Boolean Functions: Using thinning, memoization, and polynomials

December 14, 2022

Professor of Computer Science

December 14, 2022

Abstract:

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.

More details

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. The complexity of a Boolean function \(f\) measures the