CiE 2008 - Regular Talk: - The axiomatic derivation of absolute lower bounds

Regular Talk:
The axiomatic derivation of absolute lower bounds

Speaker:	Yiannis Moschovakis
Slot:	Fri, 11:40-12:00, Amphitheater A (col. 1)

Abstract

I will outline a method for deriving lower bounds for the complexity
of problems (especially in arithmetic) which are absolute
(universal), i.e., they apply to all algorithms; the key idea is to
derive lower bounds from three axioms for algorithms, which are
natural and easily shown to apply to all known models of computation.

Regular Talk: The axiomatic derivation of absolute lower bounds

Abstract

Regular Talk:
The axiomatic derivation of absolute lower bounds