Our groups focus on top-level research in theoretical computer science and discrete mathematics, with motivation from and impact into certain applied areas. Current computer science needs to deal with new challenges arising from extremely large data sets, huge software and web systems, etc. Successful methods in this new research area are often based also on new theoretical results. Theoretical computer science aims to design new algorithms and algorithmic methods to solve challenging 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. In many practical applications the goal is to optimize some outcome so our group also studies various optimization techniques. Discrete mathematics is a field closely related to theoretical computer science, it provides lots of foundational results which among others serve as basis for various algorithms. Over the past two decades our Center of Excellence – Institute for Theoretical Computer Science provided an umbrella for those activities.
Complex networks and systems are studied by the world-class mathematician Jaroslav Nešetřil using the support of ERC Synergy Grant “Dynamics and Structure of Networks”. Limits of efficient algorithms are studied by the team of Michal Koucký using the support from ERC Consolidator Grant "Lower bound for combinatorial algorithms and dynamic problems" . This research and research on approximation algorithms is supported by the follow-up five year GAČR EXPRO project "Efficient Approximation algorithms and circuit complexity" headed by Michal Koucký. The four-year European project H2020-MSCA-RISE-2019 "Combinatorial Structures and Processes" headed by Martin Loebl brings together researchers from structural discrete mathematics, algorithms and their complexity, probability and statistical physics. Since 2018, the seven year University Research Center (UNCE) project "Centre for Modern Computer Science" is running at the Faculty, headed by a renown expert in online algorithms Jiří Sgall. The group is also coordinating several Junior grants of GAČR.
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 algorithms, 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. Important part of the research includes applications to statistical physics and optimization by enumeration. Our core researchers focusing on algorithms and optimization are Jiří Sgall, Martin Loebl, Milan Hladík, Petr Kolman, Andreas E. Feldmann, Hans Raj Tiwary, Michal Koucký, Martin Koutecký, and Robert Šámal.
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, and in extension complexity. We have also excellent results in the related field of cryptography. Computational complexity and cryptography is the research focus of Michal Koucký, Zdeněk Dvořák, Pavel Hubáček, and Hans Raj Tiwary.
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. Ondřej Čepek and Petr Kučera are our principal researchers in this area.
Combinatorics and graph theory models discrete situations, relations and structures, usually involving only finitely many objects. There are many applications to the society outside of academia for example in modeling large networks but there are also important applications for other sciences such as physics and biology. The group has excellent results in structural graph theory, graph and hypergraph colorings, in Ramsey theory and in intersection of combinatorics and computational complexity. Combinatorics and graph theory is studied by Jaroslav Nešetřil, Zdeněk Dvořák, Robert Šámal, Martin Loebl, Tereza Klimošová, Jiří Fiala, Martin Balko, and Jan Hubička.
Geometry is perhaps the oldest branch of mathematics, but discrete and computational geometry is much younger. It is busy with questions on possible configurations of points, lines, curves and so on, and with their computational aspects. This problems are also important from the complexity point of view. The group has excellent results on both geometric and topological graphs, in graph drawing, in computational geometry, in topological methods in combinatorics, in geometric Ramsey theory. Discrete geometry and topology is the main focus of Pavel Valtr, Jan Kynčl, Martin Balko, and Vít Jelínek.
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 Petr Gregor and Jiří Fink.
R. Aharoni, M. Loebl: The Odd Case of Rota's Bases Conjecture. Advances in Mathematics 282 (2015) 427-442
M. Balko, J. Cibulka, P. Valtr: Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences. Discrete and Computational Geometry 61(2): 325-354 (2019)
E. Boyle, R. Cohen, D. Data, P. Hubáček: Must the Communication Graph of MPC Protocols be an Expander? 38th Annual International Cryptology Conference, Advances in Cryptology - CRYPTO (3) 2018: 243-272
Z. Dvořák: Thin graph classes and polynomial-time approximation schemes. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, SODA 2018: 1685-1701.
P. Gregor, S. Jäger, T. Mütze, J. Sawada, K. Wille: Gray Codes and Symmetric Chains. 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018: 66:1-66:14.
D. Chakraborty, D. Das, E. Goldenberg, M. Koucký, M. Saks: Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018: 979-990. Best paper award.
M. Hladík: How to determine basis stability in interval linear programming. Optimization Letters 8 (1), 375-389, 2014.
J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner: Embeddability in the 3-Sphere Is Decidable. J. ACM 65(1): 5:1-5:49 (2018).
J. Nešetřil, P.O. de Mendez: Sparsity. Springer, 2014.
P. Veselý, M. Chrobak, L. Jez, J. Sgall: A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019: 123-142.
Charles University
Ovocný trh 5
Prague 1
116 36
Czech Republic
CU Point - Centre for Information, Counselling and Social Services
E-mail:
Phone: +420 224 491 850
Erasmus+ info:
E-mail:
|
|
|
| ||
