Logical Approaches to Computational Barriers

The axiomatic derivation of absolute lower bounds

Speaker:
| Yiannis Moschovakis |

Slot: |
Array, 11:40-12:00, col. 1 |

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.

websites: Arnold Beckmann | 2008-05-19 |