Yiannis N. Moschovakis (UCLA, USA), Relative complexity in arithmetic and algebra
Schedule
- Jan. 30, 2012, 11:00 - 12:30: part 1
- Jan. 31, 2012, 11:00 - 12:30: part 2
Abstract
The main aim of these lectures is to show how ideas from the study
of recursive programs and algorithms can be used to derive lower
complexity bounds for mathematical problems which are robust (with
respect to the choice of computation model) and plausibly
"absolute", i.e., they restrict "all algorithms". An alternative
name for them would be "Recursion and Complexity".
There will be four, 40-minute lectures, as follows:
- Recursive (McCarthy) programs. Mostly well-known introductory
material. One possibly novel idea is a new approach to the
foundational problem of justifying the Church-Turing Thesis,
which comes from examining the connection between recursion and
computation.
- Uniform processes. A simple, axiomatic approach to the theory
of algorithms from specified primitives in the style of "abstract
model theory". Uniform processes capture the "uniformity" of
algorithms---that they apply "the same procedure" to all
inputs---but not their effectiveness. They carry natural
complexity measures and support a simple "Homomorphism Test" which
can be used to derive absolute lower bounds for algorithms from
specified primitives. This is the main, new material in these
lectures.
- Lower bounds in arithmetic. Strong versions of results
obtained jointly with Lou van den Dries, mostly about the
complexity of coprimeness from various primitives and relative to
various computation models.
- Lower bounds in algebra. Strong versions of results on
"0-testing" for polynomials over various fields, mostly due to Peter Buergisser
(with others) for algebraic decision trees.
Attachments
The main aim of these lectures is to show how ideas from the study of recursive programs and algorithms can be used to derive lower complexity bounds for mathematical problems which are robust (with respect to the choice of computation model) and plausibly "absolute", i.e., they restrict "all algorithms". An alternative name for them would be "Recursion and Complexity".
There will be four, 40-minute lectures, as follows:
- Recursive (McCarthy) programs. Mostly well-known introductory material. One possibly novel idea is a new approach to the foundational problem of justifying the Church-Turing Thesis, which comes from examining the connection between recursion and computation.
- Uniform processes. A simple, axiomatic approach to the theory of algorithms from specified primitives in the style of "abstract model theory". Uniform processes capture the "uniformity" of algorithms---that they apply "the same procedure" to all inputs---but not their effectiveness. They carry natural complexity measures and support a simple "Homomorphism Test" which can be used to derive absolute lower bounds for algorithms from specified primitives. This is the main, new material in these lectures.
- Lower bounds in arithmetic. Strong versions of results obtained jointly with Lou van den Dries, mostly about the complexity of coprimeness from various primitives and relative to various computation models.
- Lower bounds in algebra. Strong versions of results on "0-testing" for polynomials over various fields, mostly due to Peter Buergisser (with others) for algebraic decision trees.