Spring Semester 2002: Advanced Topics in CS, 236605

Computing over the Reals

NEW: Course material

Copies of the handwritten slides are available in the library folder 236605.
Manifesto on emancipatory aspects of doing mathematics.
Short abstracts of lectures and tirgulim.
Draft of a book by K. Meer and J. Makowsky on the subject
Projects
Slides of the course "Combinatorial counting", 236 605 (Spring 2001)

Lecturer: Prof. J.A. Makowsky (e-mail: janos@cs.technion.ac.il, room: Taub 628, tel: 4358)
Tirgul: Prof. J.A. Makowsky
Time: Wednesday 9:30-10:30 Tirgul, 10:30-12:30 Lecture
Place: Taub 8
Prerequisites: Students should feel a bit familiar with basic mathematics (Algebra and Numeric Analysis), with Computability (236343) and a bit with Logic 1 (234292).
Homepage: http://www.cs.technion.ac.il/~janos/COURSES/Reals/a2002.html

Short description

Classical computability and Complexity Theory deals with computations on strings (Turing) or on the natural numbers (Skolem, Goedel). These two approaches are easily seen to be intertranslatable. On the other hand the set of properties of the natural numbers expressible in First Order Logic is undecidable, i.e. not computable (Goedel). This stands in contrast to the real numbers, where the set of First Order properties is decidable (Tarski), but where several, competing and mutually incompatible, theories of complexity have been developed.
In the course we sketch the basics of computation theory and complexity theory over the reals (and related algebraic structures). We discuss several models of computation, their associated notions of reductions and their inherently difficult problems.
This is an active subject of research with various topics for M.Sc. and Ph.D. theses.

Related Courses:
Related courses are Definability and Computability (236331) and Algebraic Complexity (236311).

Requirements:
Homework and final project. Final exam optional.

Literature:
Most of the course will follow closely

[BCSS] L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation, Springer 1997
[H] John Harrison, Theorem Proving with the Real numbers, Springer 1998

For additional reading, one may look into

P. Buergisser, M. Clausen and A. Shokrollahi, Algebraic Complexity Theory, Springer 1996
P. Buergisser, Completeness and Reduction in Algebraic Complexity Theory, Springer 2000
E. Engeler, Algorithmic Properties of Structures, World Scientific, 1993.
B. Poizat, Les Petits Cailloux, Alea, 1995.
M. B. Pour-El and J.I. Richards, Computability in Analysis and Physics, Springer 1989
C. Smorynski, Logic Number Theory I: An Introduction, Springer 1991
J. Traub, G. Wasilkowski and H. Wozniakowski, Information Based Complexity, Aacademic Press, 1988.
Klaus Weihrauch, Computable Analysis, An Introduction. Springer 2000
Ker-I Ko, Complexity Theory of Real Functions, Progress in Theoretical Computer Science, Birkhauser, 1991
Fabrizio Broglia (Ed.), Lectures in real Geometry, De Gruyter Expositions in Mathematics vol. 23, Walter de Gruyter, New York 1996