General Information

---

Project Description

We are working on a project with our advisor Periklis Papakonstantinou. As a group we also have our own projects to solve and a couple of pending papers to attend to. Our group consists of Jarda Hančl, Matěj Konečný, Jakub Pekárek, Václav Rozhoň, Jakub Svoboda, Štěpán Šimsa and myself.
We are working with our advisor on the group-isomorphism problem:

Group Isomorphism: It is known that if graph isomorphism is NP-complete, then the polynomial hierarchy collapses to Σ2. We would like to obtain a similar result for group isomorphism under the assumption that it is NSC2-complete.

Moreover we are working on following problems from Prague:

Ramsey Numbers of 01-matrices: We are interested in Ramsey numbers of sparse 0-1 matrices, i.e. given (say permutation) square matrix P (of dimension k), how large must a square table be such that for any colouring of its cells with two colors, one can find a subtable k×k subtable such that it is monochromatic wherever P has ones.

Parametrized Graph Decomposition: Given a small (constant) graph H and a large graph G with n vertices, find an FPT algorithm (parametrized by modular width of G) for decomposing the vertex set of G into induced subgraphs isomorphic to H.

---

Week 1:

We met our advisor Periklis and he told us general overwiew of problems that he has for us. We have made a little progress on the problem with Ramsey numbers.

Week 2:

We had presentations about two of our problems on Monday. We are trying to understand problems and read some papers and a complexity textbook. We met our advisor and tried to solve some basic parts together. We have made a little bit progress in our matrix problem and I have acquired further knowledge about complexity theory.

Week 3:

We are working mostly on Group Isomorphism Problem.

Week 4:

We have good progress in Group Isomorphism Problem (see Jakub's page). We also try to found some results in Ramsey numbers, we found a linear upper-bound for some kind of permutation matrixes (permutation matrixes where each 1 is extend to identity matrix of the same size) and a lower-bound for some specific matrixes.

Week 5:

Vasek realized that there could be two possible definitions of hierarchy over SC₂. We tryied to explore which one is better and how strong is their power.
In Ramsey numbers we are working with the shortest paths containing all ones in permutation matrixes and we are thinking that they could give us a lower-bound for Ramsey number.
We had a trip to IBM on Friday.

Week 6:

We found out that we can't easily use shortest paths to create lower-bounds for some matrixes except identity matrices and we decided that we don't have enough time to explore this way to details. We started thinking about writing a paper and what should we invent to complete our knowledge a little bit more.

---

Presentations

Ramsey numbers
Group isomorphism

---

References

---