Implicit Computational Complexity: From Theory to Practice

Implicit Computational Complexity (ICC) complements traditional complexity theory through machine-independent characterizations of complexity classes. These characterizations aim at defining syntactic restrictions, embedded in a programming language, to guarantee runtime behavior; typically, complexity. Thus, ICC temporally shifts complexity to an apriori design consideration. Over the past thirty years, various ICC systems have been developed; however, they have largely remained at a theoretical level. This is discouraging in two ways. First, it prevents validating the techniques in real-world scenarios and assessing their full potential. Second, it restricts the spread of ICC techniques to wider research communities that could benefit from them. This presentation discusses a valiant effort to overcome the above challenge. It presents the applications of ICC we have discovered so far, in static analysis and in guaranteeing extended semantic properties in compiler transformations and software security. It also highlights the obstacles in bridging fruitful collaborations between separate research communities and reflects on strategies of success.