General Information

---

Project Description

I am a part of Czech group consisting of Jana Novotná, Jakub Pekárek, Václav Rozhoň, Jakub Svoboda, Matěj Konečný, Jarda Hančl (our graduate advisor) and me. Our Rutgers' advisor is Periklis A. Papakonstantinou under whose supervision we are going to work on Group isomorphism and SAT problems. Besides that, we brought a couple of other problems from The Czech Republic:

Group isomorphism

For graphs there is a theorem that says that if group isomorphism is $\textrm{NP}$-complete the polynomial hierarchy collapses to the second level. Our goal is to devise similar theorem about group isomorphism but in some sense stronger. Specifically we want to show that if group isomorphism is $\textrm{NSC}_2$-complete then some other hierarchy collapses. And to finish the argument we should also argue why that would be unexpected.

SAT heuriistics:

There are different heuristics for solving sat. Our goal would be to propose some mechanisms how to argue about them more precisely. E.g. we would like to say something like "Heuristic $A$ is better than heuristic $B$ because its running time is smaller on almost all inputs". But of course it would have to be something less restrictive so that we can compare at least something.

Ramsey Numbers of 01-matrices

You have a $0,1$ matrix $M$ and you want to find the number $R(M)$ such that for any $n\ge R(M)$ the matrix of size $n\times n$ colored in two colors contains a submatrix that is monochromatic on the positions where $M$ contains number $1$.

Parametrized Graph Decomposition

Given a small (constant) graph $H$ and a large graph $G$ with $n$ vertices, find an $\mathrm{FPT}$ algorithm (parametrized by modular width of $G$) for decomposing the vertex set of $G$ into induced subgraphs isomorphic to $H$.

Graphs without $2K_2$

A graph $2K_2$ is a graph on $4$ vertices with two independent edges. A weakly $2K_2$-free graph is a graph such that no four vertices induce a $2K_2$ graph. There exists a simple argument showing that the chromatic number of such a graph is at most quadratic in respect to its maximal clique. There is no construction showing existence of a weakly $2K_2$-free graph with quadratic chromatic number, nor is there a better bound showing that it is in fact subquadratic. Our aim is to partially fill in this gap.

---

Log

Here follows the log of our progress in more or less chronological order. There is certainly not everything we did. Specifically as I spent most of my time working on the group isomorphism problem there are probably parts missing about the other problems.

Show problems:
Group isomorphism
SAT heuristics
Ramsey on matrices
Graph decomposition
Graphs without $2K_2$

Graph decomposition:	We spend part of a day working on this problem. The problem was presented to us with the suggestion to solve it for $H=K_3$. We tried that but instead we ended up solving the problem for any $H$ with constant modular width. But later we found out that our result is not that good because the algorithm is in class $\mathrm{XP}$ and not $\mathrm{FPT}$ as we needed. I.e. the parameter (modular width) is in the exponent, the complexity is $\mathcal{O}(n^{f(w)})$, where $w$ is the modular width. But we need to find an algorithm running in $\mathcal{O}(f(w)\cdot n^{\mathcal{O}(1)}$) instead.
Graphs without $2K_2$:	We went over the (known) argument why chromatic number is at most quadratic in respect to the clique number. Then we tried to approach the problem for some time but every direction we tried failed, so far.
Ramsey on matrices:	We went over the proof why quadratic matrix is enough for the permutation matrices, how to do identity matrix in $2k$ with pigeonhole principle and why is the Ramsey number generally exponential. We are looking at some specific matrices (not just permutation matrices) and we are trying to compute their Ramsey number. For example to pigeonhole principle generalizes to several more examples.
Group isomorphism:	We had several meetings with Periklis where he explained us the problems. He talked about groups and defined several things like Cayley graphs, he told us the Alon-Roichman theorem which says that if you select $c\cdot \log(n)$ random elements of a group then with constant probability it is going to be a generating set and its Cayley graph is going to be an expander. He showed us why group isomorphism is in $\mathrm{NSC}_2$. He talked a bit about the polynomial hierarchy and why $\Sigma_2=\Pi_2$ implies the collapse of the hierarchy.
SAT heuristics:	During the same meetings with Periklis we also talked about the SAT problem. For this problem we needed to understand how we can achieve better time complexity than the trivial $\mathcal{O}(2^n)$ using random walks and restarts. We learned how to use Markov chains for this and what is coupling which could be relevant for comparing different heuristics. Periklis presented some simple (but as I understood it used in practice) heuristics and proposed we should try to find simple formulas for which one behaves better than the other.
Ramsey on matrices:	We were able to find the Ramsey numbers for more matrices. We can do identity matrix with constantly many ones in different places. We also started to distinguish between two types of Ramsey numbers – if you make the condition on the color in which you want the monochromatic submatrix or not. Specifying a color means to either find the submatrix in that color or find a submatrix $k\times k$ monochromatic in the second color (not only on the positions with ones). This allows us to combine the results better but on the other hand we cannot do even the simple line in subquadratic size.
Graphs without $2K_2$:	We used python with sage and some public database of all nonisomorphic graphs to generate all the graphs of size up to ten without $2K_2$. Up until know we where not able to find any graph with chromatic number minus the clique number being more than 1. The program found a graph where this difference is two and we were able to generalize it to constructing a graphs with clique number $k$ and chromatic number $\frac{3}{2}k$.
Group isomorphism:	There are a lot more things we need to understand about this problem. Periklis explained why graph nonisomorphism is in the IP protocol and also why it is in the AM protocol. The second part was not easy at all and we are even sure about the proper definitions of these classes. We also met with Eric Allender who gave us his insights into the topic but we are not able to follow everything as we are not that familiar with lot of the complexity theory involved.
SAT heuristics:	We were finally able to finish some exercise for computing the expected running time of the SAT algorithm (so far without any heuristics). We understood the difference between two heuristics that Periklis showed us in the beggining and which we want to compare (first) and what are the cases when one could behave worse/better than the other one. We tried to construct some simple formulas that would achieve this and after some brainstorming with Periklis we found some promising formulas. But we spend quite some time thinking about them and there was always some catch why it wasn't obvious if this will in fact work or not.
Ramsey on matrices:	We derived a method which we call "block scheme" that can be used to find a line. We are also able to find union of two permutation matrices in matrix of size $\mathcal{O}(k^4)$.
Ramsey on matrices:	Using the block scheme we can also construct several parallel lines and with some tricky computations we were able to show that the Ramsey numbers of an interesting class of matrices is polynomial. The class includes all matrices that have only constantly many ones in every column (or we can say the same thing for rows). Notice that this includes a union of constantly many permutations.
Group isomorphism:	We are spending lot of the time by reading the book about complexity theory. With more knowledge we are able to go over some parts that were unclear before. Independently Periklis explains us the last part of the proof of the theorem about graph isomorphism with the collapse of the hierarchy. But we are still not able to follow very much are at least not to verify the proofs.
SAT heuristics:	As we were unable to analyze the formulas in hand we created a program that does some computation for us. If we give it a formula and a heuristic function it constructs some Markov chain which we then use to find a lower and upper bound on the average time steps needed in our algorithm. So far, we are not considering restarts and we need to plugin specific heuristic functions (so we do the computation for several constants). With the help of the program we were able to find a formula that seems to behave much better with one heuristic than with the other.
Graphs without $2K_2$:	Jarda came with a nice idea. In the original proof of chromatic number being quadratic in the clique number there are two types of colors – single color (vertices named by a single vertex in the maximum clique) and double color (vertices named by a pair of vertices in the maximum clique). Jarda showed that when you have two double colored vertices there is a nice structure between them.
Ramsey on matrices:	We have more results for this problem but I am spending my time on the group isomorphism problem or if not then on the SAT problem.
SAT heuristics:	We are still unable to prove any of the experimental results from the computer program rigorously. We used the program to find even simpler formula then we had before but now it even doesn't make sense to us on the intuitive level and we are still unable to prove anything. Moreover, we are now spending most of the time on the group isomorphism problem.
Group isomorphism:	Vasek and some other people now finished reading most of the book and they understand everything much better. When we go over the relevant parts for several times I am also feeling much more confident in how it works.
Group isomorphism:	We derived an IP protocol for group nonisomorphism with bounded space. It is very similar to the graph nonisomorphism protocol and basicaly the thing that we wanted to do from the beginning works. But we had to resolve some details which we solved with some heavy machinery (some hard algorithms) but it seems it works.
Group isomorphism:	We have also the AM protocol. It is again based on the protocol for graphs but it is now even more complicated. We are very happy, this is nontrivial result!
Group isomorphism:	We present our proofs to Periklis and Eric. They are also enthusiastic but we still need to finish the last part, the collapse of the hierarchy. We didn't have much time to think about that yet but we speak about that with the mentors and it is not clear how to finish it but hopefully it will work.
Group isomorphism:	We found out that it is not at all clear how to define the hierarchy and the protocols for bounded space. Some definitions that are the same for polynomial space bound and for $\log$ space bound are different for our $\log^2$ space bound. We are trying to understand what is the difference between them, how strong they are, what is the "correct" definition we want to use and what we actually used in the interactive protocols.
Group isomorphism:	We found out that the hierarchy we are using is very strong. Specifically, $\mathrm{NP}$ lies in our $\mathrm{AM}$ protocol. This also means that our previous results about group nonisomorphism being in $\mathrm{AM}$ are not that cool anymore. It is still something new but the claim is not that strong anymore. But worse it seems that we will be unable to finish the proof.
Group isomorphism:	We were trying to somehow work around the problems but we are now more or less convinced that what we showed about group nonisomorphism cannot be directly used for a collapse of our hierarchy. We are writing up in sketches everything we done so that it is possible to return to this problem at some point.

For more details or for the progress from perspective of other people, don't forget to look at the logs of other Czech participants.

---

References

• [1] Squarability of rectangle arrangements, arXiv:1611.07073 [cs.CG]