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.
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.