General Information

Student:Vaclav Rozhon
Office:CoRE 444
School:Computer Science Institute of Charles University in Prague
Project:Graph isomorphism, Ramsey numbers of matrices and other projects

Project Description

We are working on a project with our advisor Periklis Papakonstantinou and also partly with Eric Allender. As a group we also have our own projects to solve and a couple of pending papers to attend to. Nice description of our projects is on the page of Jakub Pekarek. The Czech group currently consists of Jarda Hancl, Matej Konecny, Jana Novotna, Jakub Pekarek, Radim Predstirany, Stepan Simsa, Jakub Svoboda and myself. Reading this blog gives you a mere glimpse of our stay at Rutgers. For more thorough description see the blogs of other team members, most notably the page of Jakub.

Week 1:
We are currently trying to get up to speed with the problems provided by our advisor, while we sieve through the problems we brought from our university's professors.
Week 2:
We made some progress in one of our project (search Jakub Pekarek's blog for 'Ramsey number of matrices'). We also spent some time studying basics of computational complexity - good understanding of the main ideas of the field will be probably necessary for approaching our group isomorphism problem.
Week 3:
I was working mainly on our group isomorphism problem. I think we are one step away from a good result.
Week 4:
This week was really productive! We have proven the containment of the group nonisomorphism problem in an analogue of the standard AM class. This is exactly the result I was thinking of the last week.
Week 5:
We have realised that there are two possible definitions of a hierarchy over class SC2. Now it seems that we are really close to finishing the proof we want (using one of these two hierarchies) but the last crucial step seems to be harder than we expected. Anyway, we have interesting results regarding the definitions and characterisations of hierarchies over SCk. The visit of IBM scheduled on Friday was interesting.
Week 6:
Unfortunately, last part of the proof seems to be beyond our reach. That being said, we have several interesting results that are worth writing down.
Week 7:
We have written down the sketches of all our results and made the final presentation.