Two algorithms in search of a type system Norman Danner Wesleyan University Friday, April 4^th, 2008 11:00 a.m. - 12:00 p.m. Fuller Labs 320 Abstract: Implicit computational complexity is the study of (elegant) machine-independent characterizations of traditional complexity classes such as the polynomial-time computable functions. A sometimes-stated hope is that such results could yield programming languages with the pleasant properties that 1. any compilable program lies in the characterized complexity class, 2. there is a program for any function in the complexity class. The reality, though, is that while a complexity class may be captured, many natural *algorithms* are not. For example, many characterizations of polynomial-time exclude precisely the kinds of recursive definitions used in insertion- and selection-sort. In this talk I will discuss current work with James Royer of Syracuse University on a functional language which captures exactly the type-2 polynomial-time computable functionals and at the same time allows for fairly natural programming. This talk will be longer on motivation and examples and shorter on proofs. ______ Norman Danner earned his Ph.D. from Indiana University Bloomington under Daniel Leivant. After a postdoctoral position at UCLA he joined the faculty of Wesleyan University in 2002, where he is currently Assistant Professor of Computer Science. His research focuses on formalisms for implicit computational complexity (ICC) and bounded arithmetic. He is currently most interested in adapting results in ICC to programming languages. Host: Prof. Daniel Dougherty Refreshments will be served. Maintained by webmaster@cs.wpi.edu Last modified: March 27, 2008

Department of Computer Science - Worcester Polytechnic Institute
100 Institute Road, Worcester, MA 01609-2280
Phone: +1-508-831-5357 - Fax: +1-508-831-5776 - cs@wpi.edu