|
Theoretical Computer Science Faculty of Mathematics and Computer Science Jagiellonian University |
| Algorithmics Research Group |
|
| Underground - Complexity Seminar |
| Tuesday: 10:15 - 11:45, room 117 |
|
This seminar arised from a spontaneous idea. Our goal is to attract people to computational complexity theory and to broaden our knowledge in this area.
Join us!
References: 1. C.H. Papadimitriou, Computational Complexity, Addison Wesley, 1994. 2. M.R. Garey, D.S. Johnson, Computers and Intractability A Guide to the Theory of NP-completeness, Freeman, 1979. 3. M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. |
| table edited by: Przemysław Broniek |
| 17.04.2007, |
Cancelled |
| 03.04.2007, Jan Jeżabek |
Interactive proof systems |
| 27.03.2007, Przemyslaw Broniek |
Polynomial Hierarchy & Beyond |
| 20.03.2007, Przemysław Broniek |
Logarithmic Space and Polynomial Hierarchy |
| 13.03.2007, Przemysław Broniek |
Functional classes and counting problems. |
| 06.03.2007, Przemysław Broniek |
Probabilistic complexity classes |
| We will continue with presenting fundamentals of computational complexity. | |
| 27.02.2007, 23.01.2007, 09.01.2007, 19.12.2006, Grzegorz Gutowski |
Aproximation |
| 05.12.2006, 28.11.2006, 21.11.2006, Jan Jeżabek |
Reductions, Completness & NP |
| 07.11.2006, Przemysław Broniek |
Computational complexity classes - Continuation |
| We will continue the study of basic properties of complexity classes. We will present Blum's acceleration, sum of classes and hierachy theorems. | |
| 24.10.2006, Przemysław Broniek |
Computational complexity classes. Hierarchy theorems. |
| We will continue with introduction to complexity theory. This time we will present basic complexity theorems concerning acceleration, hierachy, and relations between fundamental classes. | |
| 03.10.2006, Grzegorz Gutowski |
Introduction to complexity theory. Computational models. |
| We will start with introducing our computational model - Turing machine. |