Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus
 
 
Underground - Complexity Seminar
Tuesday: 10:15 - 11:45, room 0117
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.  
 
 
  webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl