Yiannis N. Moschovakis (UCLA, USA), Relative complexity in arithmetic and algebra


  • Jan. 30, 2012, 11:00 - 12:30: part 1
  • Jan. 31, 2012, 11:00 - 12:30: part 2


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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.