DEPARTMENT OF MATHEMATICS
 UNIVERSITY OF CRETE
Knossos Ave, GR-714 09 Iraklio, Greece. Tel: +30 (0)810393801 Fax +30 (0)810393881

Seminar Program

Announcement:
In Spring 2001-02 I am organizing the Seminar "Results in Theoretical Computer Science". In this, we will try to describe some central mathematical problems and results in Theoretical Computer Science of the last twenty years or so.

We will be meeting on Wednesdays at 6:10 pm in room Z 301 and the specifics of each talk will be announced at the usual location for the Analysis Seminar. The duration of the talks will be 50 minutes.

Some of the topics we hope to cover are the following:

  1. NP-completeness and reductions
  2. Polynomial systems over the reals (quantifier elimination)
  3. Randomized algorithms and derandomization
  4. Primality testing / factorization
  5. Convex hull algorithms
  6. The Fast Fourier Transform and applications
  7. Algorithms for parallel computers
  8. The LLL lattice reduction algorithm
  9. Approximate counting using Markov Chains
  10. Lower bounds for circuit complexity
  11. Algorithmic applications for low-distortion geometric embeddings
  12. The undecidability of the tiling problem
  13. The quantum model of computation
  14. Information theory and lossless data compression
  15. Data encryption
The actual choice will of course depend very much on the various speakers' tastes.

If you'd like to speak, please contact me.

February 4, 2002

Program

Most recent up

Location Title Speaker
Wed 22/5/02, 18:10 in Z301 The LLL algorithm and applications (Part II) Nikos Tzanakis
Wed 15/5/02, 18:10 in Z301 The LLL algorithm and applications (Part I) Nikos Tzanakis
Wed 17/4/02, 18:10 in Z301 Algorithmic applications of low-distortion geometric embeddings Apostolos Giannopoulos
Wed 10/4/02, 18:10 in Z301 Expander graphs and probability amplification Mihalis Kolountzakis
Wed 3/4/02, 18:10 in Z301 Randomized complexity classes Mihalis Kolountzakis
Wed 27/3/02, 18:10 in Z 301 The Miller-Rabin probabilistic algorithm for testing primality Michel Balazard
Wed 20/3/02, 18:10 in Z 301 The computational complexity of some problems in Number Theory: Elementary operations and divisibility Thanases Pheidas
Wed 13/3/02, 18:10 in Z301 More on circuit complexity Mihalis Kolountzakis
Thu 7/3/02, 19:10 in Z301 Lower bounds for circuit complexity Mihalis Kolountzakis
Wed 27/2/02, 18:10 in Z301 A decision procedure for polynomial equations over the reals Vaggelis Felouzis
Thu 21/2/02, 19:10 in Z301 Relativization of the P vs NP question Mihalis Kolountzakis
Wed 13/2/02, 18:10 in Z301 The complexity class NP Mihalis Kolountzakis

Mihalis Kolountzakis