The research: Algorithmics

With the aim of efficient solving of NP -hard optimization problems, our algorithmic group has contributed to several approaches: (1) approximation, (2) special cases/fixed-parameter tractability, (3) exact algorithms (avoiding exhaustive-search if possible). The group aims at improving the best known results for natural graph problems by matching or breaking some natural barriers (e.g., to get a 4/3-approximation for TSP). Results in this vein were obtained recently by M. Mucha (who improved the graphic TSP approximation to 1.444), and by our PhD students (Cygan et al., FOCS 2011), who matched the barrier of the Strong Exponential Time Hypothesis for a number of problems (e.g., Hamiltonian path).

Another focus is on word algorithms and combinatorics on words. Plandowski obtained the best known algorithm (PSPACE) for solving equations on words, but the exact complexity status of this problem as well as the lower bound for the size of minimal solutions remain open. It is planned to show that the latter is (at most) exponential, which would also settle the complexity (NP). The problem for 2-dimensional words, starting from a simpler problem of string-matching, will also be studied. While this problem is NP-hard, a search will be made for algorithms using alternative representations (compression LZ, automata, etc.). Another topic concerns the number of repetitions and runs in words. Rytter, who contributed to the estimation of these numbers for words, plans to address an analogous problem for trees, where the combinatorics is much harder.

Another fascinating research project developed by Sankowski in collaboration with La Sapienza (Rome), ETH Zurich, and other centres, concerns algorithms for networks (including socio-economic networks) viewed from the broader perspective of the Science of Complex Systems. The ultimate goal here is to find the right mathematical model of a network. Michalak addresses this problem from the perspective of artificial intelligence, following the ideas of his paper at IJCAI 2011.

The group led by Dziembowski will pursue research in cryptography and data security. Their long-term goal is to contribute to the understanding of the mathematical foundations of this area. More precisely, they will focus on the leakage-resilient cryptography (work by Dziembowski et al. at FOCS’08). This new field, currently developed intensively at several top-notch institutes such as MIT, Weizmann Institute of Science, or Microsoft Research New England, aims at constructing cryptographic schemes provably secure against the so-called side-channel attacks. The goal is to come up with realistic security models and efficient constructions that are secure in them. They will also work on the information-theoretic security, in particular, quantum cryptography, in collaboration with the Faculty of Physics of the University of Warsaw.