Research
I have always admired mathematics hidden behind computers and this led my studies and research into the realm of theoretical computer science. Out of this wide scope, I find particularly attractive areas where geometry comes into the game - like graph drawing, linear and semidefinite programming in combinatorial optimization or metric embeddings, among many others.
During my PhD studies I focused on a project contributing to bridging computer science and algebraic topology. As it has been the most active part of my research for at least last three years, I exclusively devote this text to its high-level overview.
It is a team work with many coauthors - Martin Čadek, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, Uli Wagner and Peter Franek (robust satisfiability). I perceive the collaborative way of research as the main factor for the success we have achieved so far. On the contrary, this text expresses my point of view and it might miss some important aspects and not cover views of other members of our team. Nobody else is responsible for its level of lucidity and possible mistakes in there.
Computational homotopy theory
Homotopy theory viewed as robust and global geometry
Invariants of algebraic topology do not distinguish two continuous maps that are homotopic, i.e. connected by a continuous deformation. Many natural questions depend only on the homotopy classes of given maps or spaces (see extendability below, for instance) and then invariants and criteria of algebraic topology apply. The area of topology that strives for understanding the world up to homotopy is called homotopy theory. Informally, it is like geometry that reflects only robust and global properties of spaces and maps. Example:
One of the key objects of its study is [X,Y] - the set of homotopy classes of maps X -> Y and its structure for particular choices of X and Y.
Applications of algebraic topology
Algebraic topology and homotopy theory belong among central parts of mathematics for almost a century. Yet, still brand new connections are being discovered. In the past decades, surprising applications of algebraic topology yielded various new results and breakthroughs in seemingly unrelated areas such as
- scientific and engineering computations (a whole new field called computational topology emerged and provided tools and solutions for data analysis, dynamical systems, computational geometry and many other real-world challenges)
- theoretical computer science (complexity lower bounds, evasiveness)
- fair divisions (their existence in various settings)
- combinatorics (estimates on chromatic number of various graphs )
- discrete geometry (embeddability of simplicial complexes in Euclidean spaces, see slides of Jiří Matoušek, not completely up to date)
The first (and partly the second) application directions above employ, among others, various sophisticated extensions of the classical concept of homology and discrete Morse theory that are in many respects polynomial-time computable and a significant amount of effort aims at making the computation fast enough for practice.
On the contrary, the last three cases involve concepts from the heart of homotopy theory that were mostly developed in a non-constructive way and/or have infinitary nature and hence the computability seemed to be beyond the reach. Yet, the algorithmic setting in the last two cases (deciding whether a given simplicial complex is embeddable in an Euclidean space of a given dimension, or computing the topological bounds on the chromatic number of a graph) was too much interesting not to rise to the challenge: we started a project contributing to computational version of homotopy theory.
Effective homology: the computational homotopy theory of spaces
One of the pioneers in this research direction is Francis Sergeraert and his collaborators who developed effective homology - a method allowing to compute complete homological information on various spaces naturally appearing in homotopy theory. The spaces typically consists of infinitely many simplices in every dimension and thus the classical method fails. A simplified version of effective homology and a high-level idea how to obtain it in the important case of the so-called Postnikov stage is sketched here. The machinery enables extracting intrinsic homotopy structure of a given space Y - it is contained in a system of spaces and maps forming so-called Postnikov system of Y. For a complete exposition of effective homology see Rubio-Sergeraert lecture notes. For the algorithm for the Postnikov system, see Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension.
Next step: from spaces to maps
To deal with maps from a space X to a space Y, it is convenient when X has the structure of a simplicial complex (or a simplicial set) but Y - with a little help from effective homology - has to be replaced by its Postnikov system. Still, more ingredients are needed: among others it is the algorithmic version of group operations on [X,Y] - the set of homotopy classes of maps X -> Y. This exists only for dim X < 2k where Y is k-connected (informally, Y has no holes up to dimension k), for instance Y is the (k+1)-sphere. This range of dimensions is called the stable range and here [X,Y] has the structure of an Abelian group and can be computed. Below we indicate that the assumption of the stable range is essentially necessary. In the end, the problem can be reduced to linear algebra over integers.
For a brief visual introduction to the [X,Y] computation, see SODA 2012 slides. For a more involved visual exposition, try ATMCS 2012 slides. For a complete exposition, see Computing all maps into a sphere.
Extendability
A direct consequence of the [X,Y] computability is the algorithm for the extension problem: In addition to the complexes X and Y as above, given a subcomplex A of X and a simplicial map f: A -> Y, the question is if there is a continuous extension X -> Y of f.
Polynomial running time for fixed dimensions
Then we developed a polynomial-time version of effective homology (see Polynomial-time homology for simplicial Eilenberg-Mac Lane spaces and Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension). This leads to a polynomial-time algorithms for
- the extension problem as well as for [X,Y] when dimensions are fixed and in the stable range;
- k-th homotopy group of a simplicial complex Y.
Time is polynomial in terms of the size of simplicial complexes X,Y and the degree of the polynomial depends on the dimension of the domain complex X or k.
Undecidability
We obtained the following hardness results that somewhat complement the above algorithmic results.
- Extendability is undecidable outside the stable range, i.e., when dim X>=2k+2 and Y is k-connected.
- It is #P-hard to compute the n-th homotopy group [S^n,Y] when both n and a simply connected simplicial complex Y are given as input. The homotopy groups are the necessary component of the Postnikov system of Y). It is an extension of a result by Anick who proved the hardness for the case when Y is a 4-dimensional cellular complex given in certain compact encoding.
The latest development is summarized in a survey Extending continuous maps: polynomiality and undecidability.
Work in progress
Computational topological combinatorics
We are also preparing the solution for the original problems that triggered off this project, that is, the existence of a Z_2-equivariant map X -> Y (a map X -> Y compatible with given Z_2 actions on X and Y). In addition, we cover even more general questions of the existence and structure of cross sections in a fiber bundle.
Robust satisfiability
In numerical and interval analysis, the famous Brower fixed-point theorem or the concept of topological degree are commonly used to verify the existence of a root of a given function R^m -> R^m. The need for the verification comes from the following sources:
- The numerical computation suffers from the rounding errors in floating-point operations,
- or the values of the function may come from an imprecise measurements or from a model with inherent uncertainty.
There are two directions for an improvement via considering extendability of maps into a sphere:
- By applying the Hopf extendability criterion, we can give more precise information on the robustness of roots of a function
We can both verify and disprove the existence of alpha-robust roots and locate them with the best possible precision. (more formal statement of the algorithmic problem robust satisfiability.) The Hopf criterion reduces to a system of linear equations over integers that can be solved efficiently.
- With the help of computational homotopy theory we can pass to functions R^m -> R^n for all m = n,...,2n-3. A visual sketch of the algorithm.
Publications and preprints
- Martin Čadek, Marek Krčál, Jiří Matoušek, Lukáš Vokřínek, Uli Wagner
Extending continuous maps: polynomiality and undecidability (a survey), extended abstract of the three papers below, to appear Proc. of the 45th ACM Symposium on the Theory of Computing (STOC), 2013. - Martin Čadek, Marek Krčál, Jiří Matoušek, Lukáš Vokřínek, Uli Wagner
Extendability of continuous maps is undecidable - Martin Čadek, Marek Krčál, Jiří Matoušek, Lukáš Vokřínek, Uli Wagner
Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension - Marek Krčál, Jiří Matoušek, Francis Sergeraert
Polynomial-time homology for simplicial Eilenberg-MacLane spaces - Ken-Ichi Kawarabayashi, Marek Krčál, Daniel Král' and Stephan Kreutzer
Packing directed cycles through a specified vertex set, Proc. of the Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2013. - Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, Uli Wagner
Computing all maps into a sphere
Extended abstract in Proc. of the 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), ACM-SIAM, 2012. - Tomáš Ebenlendr, Marek Krčál, Jiří Sgall
Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines in Algorithmica 2012.
Early version in Proc. of the 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), ACM-SIAM, 2008.
- Marek Krčál
Collapse closed classes of graphs and graph parameters
Master degree thesis, Faculty of Exact Sciences, VU University Amsterdam, 2008. - Marek Krčál
Computational complexity of graph planarity testing
Bachelor Thesis, Faculty of Mathematics and Physics, Charles University Prague, 2006.