Mahematics 290D, Complexity lower bounds, Fall 2008 and Winter 2009, Moschovakis

Instructor: Yiannis N. Moschovakis, MS 7907, ynm@math.ucla.edu
Meetings (for Winter 2009): Tuesday, 3:00 - 6:00, MS 5127

General information about the class

Lectures in Fall 2008:

1. Tuesday, October 7: Anush Tserunyan: Recursive programs (2)
2. Tuesday, October 14. Anush continues.
3. Tuesday, October 21. Jennifer Padilla: Sorting (1)
4. Tuesday, October 28. Justin Palumbo: The Fischer-Rabin Theorem (4)
5. Tuesday, November 5. Justin continues.
6. Thursday, November 13, 3:00 - 5:00, MS5147 (check here to verify room)
                    Viraj Navkal: Optimality of the Horner rule (3)
7. Tuesday, November 18, Konstantinos Palamourdas: Lower bounds for
                    primality from  Presburger givens (Sections 2 and 3 of 5
                    and parts of 6)
8. Tuesday, November 25, Ngoc Le: Optimality of the Stein algorithm, good examples
                    (Section 4 of (5) and Section 6 of (6))
9. Tuesday, December 2, Moschovakis: Lower bounds from axioms for algorithms (7)

Lectures in Winter 2009:

1. Tuesday, January 6, Konstantinos Palamourdas: Unary decision problems from
division with remainder (Section 7 of (6) and (7))
2. Tuesday, January 13, Jennifer Padilla: A little number theory (Section 8 of (6))
3. Tuesday, January 20, Justin Palumbo: Coprimeness from division (Section 5 of (5))
4. Tuesday, January 27, Anush Tserunyan: Primes in NP (8)
5. Tuesday, February 3, Anush continues with (9)
6. Tuesday, February 10, Ngoc Le, Primes in P (10).
7. Tuesday, February 17, Ngoc continues
8. Tuesday, February 24 at 4:00, Konstantinos Palamourdas on logical extensions
(Sections 6 of (5) and 13 of (6))

Basic material:
1. Sorting: 1 and 2
2.Recursive programs
3.S. Winograd. On the number of multiplications required to compute certain functions
4.Michael J. Fischer and Michael O. Rabin. Super-exponential complexity of Presburger arithmetic.
5.Lou van den Dries and Yiannis N. Moschovakis. Is the Euclidean algorithm optimal among its peers?
6. Y. Moschovakis. Arithmetic complexity (lecture notes from a class)
7. Y. Moschovakis, The axiomatic derivation of absolute lower bounds
8. Vaughan Pratt, Every prome has a succint certificate
9. Vaughan Pratt, Euclidean gcd is exponentially suboptimal, ...
10. M. Agrawal (and others), Primes in P.