General Information
| Student: | Jakub Pekárek |
|---|---|
| Office: | CoRE 442 |
| School: | Computer Science Institute of Charles University in Prague |
| Projects: |
|
| 2016 project |
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. The czech group consists of Jarda Hančl (our coordinator and benevolent ruler), Matěj Konečný, Jana Novotná, Radim Předstíraný, Václav Rozhoň, Jakub Svoboda, Štěpán Šimsa, and myself.
Group Isomorphism
A project we work on in cooperation with our advisor, see our introductory presentation.
There exists a theorem that if graph isomorphism problem is NP-complete, then polynomial hierarchy of complexity collapses down to a level 2 (PH $= \Delta_2 = \Sigma_2 = \Pi_2$). As the polynomial hierarchy is believed to exist, this is considered as an evidence that graph isomorphism is in fact easier though we have no algorithm as a witness. The proof is based on iterative protocol paradigm, namely Arthur-Merlin type of protocols.
The group isomorphism can be solved in $NSC^2$ which is incomperable with P. However unless group isomorphism is in P, it has to be very hard problem in $NCS^2$, most likely $NCS^2$-complete. While $NCS^2$-complete problem would be much easier class than NP-complete one, we hope to adapt the same ideas to provide evidence for group isomorphism to be in fact in P. Our goal is to show that if group isomorphism is harder, then a different kind of hierarchy in between P and NP would collapse, bringing P and NP a little closer together.
SAT Heuristics Analysis
Another project we work on in cooperation with our advisor.
Our aim in this project is to construct an analysis framework to estimate performance of heuristics in random SAT solving. The details are rather technical and not yet in place.
Ramsey Numbers of 01-matrices
This problem we brought from Prague, see our introductory presentation presentation.
Suppose we have an k times k template matrix of zeros and ones, where the ones form our template. Then the ramsey number of such a matrix is the nimimal number n such that every table of size at least n times n with its cells colored by two colors contains a monochromatic template. In other words, there exists a selection of k rows and k colums from the table such that all ones from the template correspond to only one color in the selection.
Ramsey number can range from linear dependence on k to exponential. We are mainly interested in permutation matrices as their ramsey numbers are at most quadratic. Our aim is to characterize subclasses of permutations with subquadratic and superlinear ramsey numbers. We are also interested in other types of sparse matrices and the treshold between polynomial and exponential ramsey number.
Parametrized Graph Decomposition
Another problem we brought from Prague.
Given a small graph H (say a triangle) and a graph G with approproate number of vertices, is it possible to split all vertices of G into groups so that each group induces exactly H? This decision problem is computationally complex, however depending on parametrization of complexity e.g. by modular width, clique-width or shrub-depth, some of these problems turn out to have different properties than others. Our aim is to explore some of the possibilities and see if we can increase knowledge about some of them.
Weakly $2K_2$-free Graph Coloring Bounds
Yet another problem we brought from Prague.
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. Such a graph is always either trivial or very dense. 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.
Simultaneous Spanning Trees
This problem was solved by members of the czech group on the Problem Seminar of Combinatorics of the Department of Applied Mathematics, Charles University.
The minimal spanning tree is a well studied problem, and is one of the computationally easiest non-trivial problems. We studied the problem of finding minimal spanning trees on several graphs simultaneously such that the spanning trees agree on an intersection of the graphs. We show a rather surprizing result that for 3 and more graphs, deciding whether solution exists is NP-complete, and we provide a polynomial-time algorithm which finds the solution for the case of two graphs, if a solution exists. We also studied simultaneous pairing problem a little bit, where the main results are more trivial.
During our stay on the REU we intend to compose our research into a paper and publish our results.
Minimal Sum Labeling of Graphs
This problem was also solved by members of the czech group on the Problem Seminar of Combinatorics of the Department of Applied Mathematics, Charles University.
A graph $G$ is called a em sum graph if there is a so-called sum labeling of $G$, i.e. an injective function $\ell: V(G) \rightarrow \mathbb{N}$ such that for every $u,v\in V(G)$ it holds that $uv\in E(G)$ if and only if there exists a vertex $w\in V(G)$ such that $\ell(u)+\ell(v) = \ell(w)$. We say that sum labeling $\ell$ is minimal if there is a vertex $u\in V(G)$ such that $\ell(u)=1$. In our paper, we show that if we relax the conditions (either allow non-injective labelings or consider graphs with loops) then there are sum graphs without a minimal labeling, which partially answers a previously open question.
Our paper is already accepted to the IWOCA conference, where it will be presented by the end of the REU by a member of the last year's czech group Martin Töpfer. Our arguments are capable of answering the previously open question in full, however we need to overcome some technical difficulties before making the last leap official.
Progress
Group Isomorphism
In our first weeks we gained a solid background in the interactive protocol paradigm, especially Arthur-Merlin protocols with public randomness. We also studied relations of classical polynomial hierarchy, alternating turing machines and space-limited computations.
Our work started with understanding the algorithm deciding group isomorphism in $NCS^2$ and its key ingredient, Reingold's algorithm.
In our attempt to accomodate the ideas of the previous algorithms and collapse theorem to design interactive protocols for group non-isomorphism achieving similar results, we face number of formal problems that are still open. We discovered a gap in the generally accepted equivalent definitions of alternation hierarchies. All the usual definitions coincide above $P$-time and below $log$-space, but not in between when our work takes place. It is therefore not clear what kind of hierarchy we are working with and which properties can be considered.
We brought forth a definition of hierarchy of iteractive protocols in $NSC^2$ settings and designed a group non-isomorphism protocol with private randomness. Our key achievement leading to this protocol is a way to compress information about permutations and group structures together with a method of extracting the structure independently of the representation of the group. This allows us to fool an all-powerful Merlin-like machine. By an compression-driven extension of the set-lower-bound protocol and a design of custom streaming hash functions we managed to create an public randomness protocol with possibility to acheve an inverse-superpolynomially small error.
We have discovered, that while other definitions of $NSC^2$-hierarchy are too weak to accomodate reasonable protocols, the definition we used creates heararchy of classes intermediate to the classes of classical polynomial hierarchy. This is a rather surprising fact making all our results reside within a very strong model, which utterly anihilates any hope for result similar to our original goal. We conclude that there is no reasonable definition of $NSC^2$ hieararchy where this build-up of power does not occur. This however brings into the light very interesting results about quantification of limited formulae which is itself worth investigating.
SAT Heuristics Analysis
We are trying to design an approach to compare heuristics. So far it seems that any behaviours we managed to analyze directly and through simulations seems to defy expectations of our advisor. Due to that fact we tried to approach the problem very broadly. This undermines our theretical basis and it is not clear what questions, if any, are woth investigating.
Ramsey Numbers of 01-matrices
We have discovered a polynomial upper bounds for matrices with at most $j$ ones in each collumn (or row) which seems very tight. This result covers much broader range of matrices than just permutations and their unions.
Other areas of interest yielded many bounds for specific patterns outside of the permutation patterns that have a linear upper bound for the Ramsey number.
We also studied matrices constructed from other matrices through some limited set of operations. We can now produce upper bound for various compositions, recursive constructions and rotations (such as 45° matrix rotation).
In the second part of our research, we devised a hypothesis describing lower bounds of general permutations. We do not know whether the link under discussion is sound, but despite a rather lack of formal and constructive relations, our quasi-experimental results show surprising precision.
It is still open whether there are any useful criteria separating permutations (or matrices in general) with linear and superlinear ramsey number.
Parametrized Graph Decomposition
In the first weeks we designed an algorithm for decomposition, however we were not able to modify in so that its complexity is polynomial not only in the imput, but also in the given parameters. This is generally considered a weak result, but result non the less. After probing the problem deeper we decided to postpone it for later due to more interesting progress in other problems.
Weakly $2K_2$-free Graphs Coloring Bounds
We invested a lot of time into understanding the nature of this peculiar problem. We uncovered facts showing that this problem and its dual are related to very well studied problems of graph theory. This of means that this particular problem is probably unexpectedly hard.
We managed to create a classification of vertices based on a diameter property of the weakly $2K_2$-free graphs and hope to use it as our main tool to characterize clique relations in the whole structure. So far it is still open what is the exact diamater characterization and whether its structure gives a useful decomposition.