CACL: Computability and automatic complexity lab

Team members

  • Bjørn Kjos-Hanssen (Professor)
  • David Webb (Ph.D. student) computability theory
  • Jack Yoon (Ph.D. student) computability theory
  • Samuel Birns (Ph.D. student) computability theory
  • Taqui Raza (M.A. student) web semantics

Recent members

  1. Achilles Beros, Temporary Assistant Professor, 2015-2019
  2. Mushfeq Khan, Temporary Assistant Professor, 2014-2018
  3. Jake Fennick, M.A. 2019
  4. Kaui Yogi, M.A. 2018
  5. Lei Liu, M.A. 2017
  6. Paul Kim Long V. Nguyen, Ph.D. 2014
  7. Malihe Alikhani, M.A. 2014
  8. Jason Rute, Junior Researcher, 2013
  9. Kayleigh Hyde, M.A. 2013
  10. Cameron Freer, Junior Researcher, 2010-2011
  11. Quinn Culver, M.A. 2010
  12. Katie Brodhead, Temporary Assistant Professor, 2008-2009

This site

In the menu above, press "Complexities" for an autocomplete-based JavaScript app. Press "Witnesses" for a screensaver.

Complexity lookup over HTTP

Other sites

Bjørn Kjos-Hanssen (WordPress)

Automatic complexity in the cloud


  • Fixed minor bug in the screensaver.
  • Complexity witnesses by HTTP now included up to length 23. Check out for example
  • New version (Javascript) goes up to length 19. All info up to that length is in memory at the same time so it is a bit slow.
  • The web app works great in Opera! Not as well in Chrome, and not at all in Firefox.
  • The autocomplete works in the Chrome browser, but not in a good way: to see the complexity of the string 0 you first have to type 000000000 then delete several 0s. The Android app is better!
  • Because I uploaded data to Google's database via HTTP, only up to length 8 was possible, so that is the current length being used.
  • Using JavaScript (JQuery) to get the data from the Google App Engine database asynchronously, thus no info available in View Source.
011000111100000110       9
means that the string 011000111100000110 has complexity 9. An Android version for 0.99 USD is available in the Google Play Store.