In their MSc thesis [1], Arvid Rydberg and Selina Sand Engberg explored the complexity of Boolean functions (functions from n bits to one bit). Measuring their evaluation cost, especially using the probabilistic level-p-complexity (D_p(f)), is an interesting computational challenge.
The students focused on implementing and improving algorithms for computing this measure.
Key Contributions
- They optimised an existing algorithm by Jansson and Jansson [2]. They achieved this by implementing techniques like hash-consing and normalisation, which effectively enhance memoization and make computations more efficient.
- They explored a few subclasses of Boolean functions: specifically symmetric and threshold functions. They developed specialized data representations that allowed for faster computations when working with these common cases.
- To gain deeper insights, they built tools to analyze the piecewise polynomial structure of level-p-complexity. They developed a method to precisely identify critical points in this structure using algebraic numbers, enabling exact calculations.
- Finally, they rigorously tested their results. They implemented properties and generators using QuickCheck, to establish confidence in the correctness of their algorithms.
Through this explorative and implementation-focused work, Arvid and Selina built a Haskell library (available on Github [3]) for future study of level-p-complexity for Boolean functions. Earlier work (before Arvid and Selina started) was described here [4] and in this talk from ICFP 2024: Level-p-complexity of Boolean Functions (Patrik Jansson).
[1] https://odr.chalmers.se/items/08a0db55-2ac0-43dc-a0c9-c0df35fab7f3
[2] https://doi.org/10.1017/S0956796823000102
[3] https://github.com/Riddarvid/BoFunComplexitySubclasses
[4] https://patrikja.owlstown.net/posts/2013
PS. The thesis work was done during the academic year 2024/25, ending in February, but the thesis was published just a few days ago: 2025-10-03.
[2] https://doi.org/10.1017/S0956796823000102
[3] https://github.com/Riddarvid/BoFunComplexitySubclasses
[4] https://patrikja.owlstown.net/posts/2013
PS. The thesis work was done during the academic year 2024/25, ending in February, but the thesis was published just a few days ago: 2025-10-03.