DEPARTMENT OF MATHEMATICS UNIVERSITY OF CRETE |

**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:

- NP-completeness and reductions
- Polynomial systems over the reals (quantifier elimination)
- Randomized algorithms and derandomization
- Primality testing / factorization
- Convex hull algorithms
- The Fast Fourier Transform and applications
- Algorithms for parallel computers
- The LLL lattice reduction algorithm
- Approximate counting using Markov Chains
- Lower bounds for circuit complexity
- Algorithmic applications for low-distortion geometric embeddings
- The undecidability of the tiling problem
- The quantum model of computation
- Information theory and lossless data compression
- Data encryption

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

February 4, 2002

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 |