Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Bruce Kapron: Type-two feasibility via bounded query revision

LFCS seminar: Bruce Kapron: Type-two feasibility via bounded query revision

— filed under: ,

  • LFCS Seminar
  • Upcoming events
When Jul 16, 2019
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal

The problem of generalizing the notion of polynomial time to a  
type-two 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 scheme-based 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 machine-based  
characterization remained open for almost two decades, when Kapron and  
Cook gave a solution using notions of function length and second-order  
polynomials. While a natural generalization of the usual notion of  
poly-time, 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 follow-up work  
involving new scheme-based characterizations of Mehlhorn's class, as  
well as a recent characterization using a tier-based 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.)

Document Actions