Patrik Jansson

Professor of Computer Science


Computer Science and Engineering

Chalmers University of Technology

More on computing Level-p-complexity with Haskell

August 16, 2023

After the earlier posts (2022-12, 2023-03) there has been some more development on the "Level-\(p\)-complexity"-front. The topic is inspired from mathematical research by Prof. Jeffrey Steif and other colleagues, but the paper (in submission to JFP) is mainly about algorithmic techniques to tame the double exponential complexity of an "obviously correct but horribly inefficient" executable specification.

First, the initial round of JFP reviews resulted in a long list of good suggestions for improvements of the paper (and an editor verdict of "accept with minor revision"). We have now worked through the paper based on the feedback and a new version is uploaded to arXiv (and re-submitted to JFP - fingers crossed!).

Second, the talk I gave at Chalmers sparked some interest: both Christian Sattler and William Hughes were inspired by my "future work challenge" to compute the level-p-complexity of the 27-bit Boolean function \(maj_3^3\) (three level iterated majority on three bits). The library described in the paper is generic (it can be applied to any Boolean function) but \(maj_3^3\) is beyond its reach. Both ChSa and LiHu then set out to explore what can be gained (speed-wise) by restricting to only "iterated threshold functions". The good news is that we now have code (on github) which can handle \(maj_3^3\)! (More work remains to ensure that the code is actually correct but preliminary results are available on github.)

We also have some other ideas about possible efficiency improvements for the computation in the generic library - there is still space for future work in this direction.


Follow this website

You need to create an Owlstown account to follow this website.

Sign up

Already an Owlstown member?

Log in