The Simons Foundation under the program Collaboration Grants for Mathematicians (#315188 to Bjørn Kjos-Hanssen, grant title “Automatic Complexity”) supported my travel during 2014–2019.
|2014 – 2015||COCOA 2014 (Maui); U. Washington; Varieties of Algorithmic Information; CCR, Heidelberg; Haidar to Arizona Winter School|
|2015 – 2016||ASL Annual Meeting, UConn (myself and Beros); SIAM Meeting on Discrete Math, Atlanta|
|2016 – 2017||WoLLIC, London; UCNC, Arkansas|
|2017 – 2018||Workshop on Computability Theory, Waterloo|
|2018 – 2019||Computability Theory and Foundations of Mathematics, Tokyo; Joint Math Meetings, Baltimore|
Here are papers produced about automatic complexity, many with Master’s students.
Conferences in parentheses are those with no published proceedings.
Students or consultants in parentheses discussed the topic but were not coauthors.
|Hyde (MA, 2013)||COCOON 2014||Elec. J. Combinatorics (2015)|
|COCOA 2014||Theoretical Computer Science (2015)|
|Alikhani (MA, 2014); Pakravan, Saadat (MSc Fin.Eng., 2013)||Algorithmic Finance (2015)|
|(written at CCR 2015)||Theory of Computing Systems (2017)|
|(Castiglione 2015)||WoLLIC 2017||Discrete Mathematics (2018)|
|(Kobayashi 2016)||(VAI 2015)||Experimental Mathematics (2019)|
|(Huggins 2016)||UCNC 2017|
|Liu (MA, 2017)||(ALH 2018)|
|Yogi (MA, 2018)|
Kolmogorov structure functions for automatic complexity
We study an analogue of Kolmogorov’s notion of structure function, introduced in 1973, with Kolmogorov complexity replaced by Shallit and Wang’s (2001) automatic complexity. We discuss the prospects for using it for model selection in statistics. We prove an upper bound which is piecewise smooth, related to the binary entropy function, and appears to be fairly sharp based on numerical evidence.