LFCS seminar: Bruce Kapron: Typetwo feasibility via bounded query revision
What 


When 
Jul 16, 2019 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
The problem of generalizing the notion of polynomial time to a
typetwo setting, where inputs include not only finitary data, e.g.,
numbers or strings of symbols, but also functions on such data, was
first posed by Constable in 1973. Mehlhorn subsequently proposed a
solution, based on a generalization Cobham's schemebased approach
which uses limited recursion on notation. The resulting class was
shown to be robust with respect to oracle Turing machine (OTM)
computation, but the problem of providing a purely machinebased
characterization remained open for almost two decades, when Kapron and
Cook gave a solution using notions of function length and secondorder
polynomials. While a natural generalization of the usual notion of
polytime, this characterization still had some shortcomings, as
function length is itself not a feasible notion. A characterization
using ordinary polynomials remained an elusive goal.
Recently, we have provided several such characterizations. The
underlying idea is to bound run time in terms of an ordinary
polynomial in the largest answer returned by an oracle, while imposing
a constant upper bound on the number of times an oracle query (answer)
may exceed all previous ones in size. The resulting classes are
contained in Mehlhorn's class, and when closed under composition are
in fact equivalent.
In this talk we will present these recent results and followup work
involving new schemebased characterizations of Mehlhorn's class, as
well as a recent characterization using a tierbased type system for a
simple imperative programming language with oracle calls.
(Joint work with F. Steinberg, and with E. Hainry, J.Y. Marion, and
R. Pechoux.)