**Subject: **Apr 10, Beklemishev & Rastsvetaev: Query Complexity and Formal Arithmetic

**From: **Wolfgang Slany (*wsi@dbai.tuwien.ac.at*)

**Date: **Thu Apr 06 2000 - 14:48:10 MET DST

**sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Norbert Preining: "Einladung zur ScienceWeek Veranstaltung der KGS"**Previous message:**Georg Moser: "General Assembly 1999"

KURT GÖDEL SOCIETY

LECTURE ANNOUNCEMENT

We are pleased to inform you that Prof. L. Beklemishev and

Prof. A. Rastsvetaev will give a lecture:

SPEAKER: Prof. L. Beklemishev and Prof. A. Rastsvetaev

Institute for Algebra and Computational Mathematics

University of Technology, Vienna

TITLE: QUERY COMPLEXITY AND FORMAL ARITHMETIC

DATE & TIME: Monday, April 10, 2000

16.45

LOCATION: Seminarraum des Instituts für Computersprachen (Prof. Leitsch)

Favoritenstrasse 9

Stiege 1

3. Stock

ABSTRACT:

In the theory of strong fragments of Peano

arithmetic it is the query complexity measure

(the number of necessary oracle queries), rather

than the more usual time or space measures, that

plays a role. In the first part of the talk these

relationships will be discussed and the example

of induction schema for decidable predicates will

be treated.

In the second part of the talk the query

complexity of the problem of finding a local

maximum point of a function on a bounded interval

will be sharply estimated. The optimal algorithm

for this problem happens to be related to the famous

Fibonacci numbers. The query complexity is then

estimated by log_c(n)+O(1), where c is the "golden

ratio" constant.

**Next message:**Norbert Preining: "Einladung zur ScienceWeek Veranstaltung der KGS"**Previous message:**Georg Moser: "General Assembly 1999"

*
This archive was generated by hypermail 2b25
: Thu Apr 06 2000 - 16:19:21 MET DST
*