Finding the shortest path between two cities takes a GPS navigation a fraction of a second. Finding the best way to pack a large number of boxes of various sizes into shipping containers is beyond anyone’s computational resources as we do not know any fast enough algorithm for this problem. What are the best algorithms for various problems? How to efficiently implement them? What makes computational problems hard to solve by an algorithm? These are some of the main questions theoretical computer science tries to answer. Hence, theoretical computer science aims to design new algorithms and algorithmic methods to solve various problems, design efficient data structures that would support fast implementation of these algorithms and understand for which problems our current algorithmic solutions are already the best possible.
The group of theoretical computer science addresses various aspects of these questions. It is supported by European Research Council (ERC) project Lower bounds for combinatorial algorithms and dynamic problems, and by other grants.
Members of the group regularly publish in the top conferences (STOC, FOCS, SODA) and top journals. We have extensive connections with top research centers abroad and also closely collaborate with other Czech groups, most notably the logic and complexity group at the Czech Academy of Sciences lead by P. Pudlák. We list several areas (and group members active in them) with outstanding results.
In the area of computational complexity we study the questions of how efficiently we can solve various computational problems, how optimal algorithms for various problems look like, what makes problems hard to solve by a computer, and where is the boundary of what can be solved efficiently. We focus on the study of boolean circuits, which is the standard model of computation, on communication complexity, which measures the amount of communication necessary to solve problems by several parties, on extension complexity, which is an approach to understanding intractable problems, on limits of efficient data structures. Our group achieved outstanding results in the area of lower bounds for various computational models, in understanding the relationship between various computational resources, in computational geometry and semidefinite programming. Computational complexity is the research focus of M. Koucký, Z. Dvořák, and H. Raj Tiwary.
For many combinatorial and other problems it is easy to find some solution, on the other hand, it is significantly harder to find a good or even optimal solution for some measures of quality. For such problems we study approximation algorithms which find, at a reasonable speed, a solution which is close to the optimal one. One of the fundamental issues for algorithm design is the knowledge of input data. We study this area in two ways: First, we study online algorithms that learn the input piece by piece but have to produce a partial output immediately. Second, we study the problems of interval arithmetic, which assumes that the numbers on input are known only with some precision. Our group has excellent results both in the area of approximation and online algorithms for scheduling and related problems, and in the area of interval arithmetic, esp. for problems of linear algebra and linear programming. We also study linear and semidefinite programming and its algorithmic applications. Our core researchers focusing on algorithms and optimization are J. Sgall, M. Hladík, M. Monemizadeh, and R. Šámal.
In representation of knowledge we study problems related to efficient knowledge representation using tools of propositional logic, namely using propositional formulas. There are various areas of knowledge representation, among those we mainly concentrate on knowledge compression and knowledge compilation. In knowledge compression our interest is to find a smallest possible (e.g. in a sense of the length of a formula) representation of given knowledge base. In knowledge compilation we want to translate the given knowledge base into a form which is suitable for answering particular kinds of queries. O. Čepek and P. Kučera are our principal researchers in this area.
Hypercubes form a class of graphs that is exploited in many applications; it is also an important model of parallel computers. Today they serve as a tool for modeling of network computers (or users). A Hamiltonian path in hypercube is a Gray code that has applications in many directions, in informational retrieval, signal encoding, image processing or data compression. Therefore we orient our research on graph properties of hypercubes with special attention to paths covering a hypercube and study of hypercubes with faulty vertices. Hypercubes are among research interests of P. Gregor.
S. Fiorini, S. Massar, S. Pokutta, H. Raj Tiwary, R. de Wolf: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12), pp. 95-106, 2012.
J. Bulánek, M. Koucký, and M. Saks: Tight lower bounds for the online labeling problem. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12), pp. 1185-1198, 2012.
M. Babka, T. Balyo, O. Čepek, Š. Gurský, P. Kučera, V. Vlček: Complexity issues related to propagation completeness, Artificial Intelligence, Vol. 203, 19-34, (2013).
T. Dvořák, J. Fink, P. Gregor, V. Koubek, T. Radzik: Testing of connectivity of faulty networks in sub linear time, J. of Discrete Algorithms, Vol. 14, 223-231, (2012).
M. Hladík, D. Daney, and E. Tsigaridas: Bounds on Real Eigenvalues and Singular Values of Interval Matrices. SIAM J. Matrix Anal. Appl. 31:2116-2129, 2010.
T. Ebenlendr, M. Krčál, J. Sgall: Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica. 68:62-80, 2014.