Theoretical computer science and combinatorics ****************************************************************************************** * Theoretical computer science and combinatorics ****************************************************************************************** Our groups focus on top-level research in theoretical computer science and discrete mathem motivation from and impact into certain applied areas. Current computer science needs to d challenges arising from extremely large data sets, huge software and web systems, etc. Suc in this new research area are often based also on new theoretical results. Theoretical com aims to design new algorithms and algorithmic methods to solve challenging problems, desig structures that would support fast implementation of these algorithms and understand for w current algorithmic solutions are already the best possible. In many practical application optimize some outcome so our group also studies various optimization techniques. Discrete a field closely related to theoretical computer science, it provides lots of foundational among others serve as basis for various algorithms. Over the past two decades our Center o 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ři iuuk.mff.cuni.cz/people/nesetril.html"] using the support of ERC Synergy Grant “Dynamics a of Networks”. Limits of efficient algorithms are studied by the team of Michal Koucký [ UR iuuk.mff.cuni.cz/people/koucky.html"] using the support from ERC Consolidator Grant "Lower combinatorial algorithms and dynamic problems" [ URL "https://iuuk.mff.cuni.cz/~koucky/LBC research and research on approximation algorithms is supported by the follow-up five year project "Efficient Approximation algorithms and circuit complexity" [ URL "https://iuuk.mf ~koucky/EPAC/"] headed by Michal Koucký. The four-year European project H2020-MSCA-RISE-20 Structures and Processes" [ URL "https://kam.mff.cuni.cz/rise/"] headed by Martin Loebl [ kam.mff.cuni.cz/~loebl/"] brings together researchers from structural discrete mathematics and their complexity, probability and statistical physics. Since 2018, the seven year Univ Center (UNCE) project "Centre for Modern Computer Science" [ URL "https://iuuk.mff.cuni.cz cmi/"] is running at the Faculty, headed by a renown expert in online algorithms Jiří Sgal iuuk.mff.cuni.cz/people/sgall.html"] . The group is also coordinating several Junior grant *========================================================================================= * Algorithms and optimization *========================================================================================= For many combinatorial and other problems it is easy to find some solution, on the other h significantly harder to find a good or even optimal solution for some measures of quality. problems we study approximation algorithms which find, at a reasonable speed, a solution w to the optimal one. One of the fundamental issues for algorithm design is the knowledge of We study this area in two ways: First, we study online algorithms that learn the input pie but have to produce a partial output immediately. Second, we study the problems of interva which assumes that the numbers on input are known only with some precision. Our group has results both in the area of approximation algorithms, and in the area of interval arithmet problems of linear algebra and linear programming. We also study linear and semidefinite p its algorithmic applications. Important part of the research includes applications to stat and optimization by enumeration. Our core researchers focusing on algorithms and optimizat Sgall [ URL "https://iuuk.mff.cuni.cz/people/sgall.html"] , Martin Loebl [ URL "https://ka ~loebl/"] , Milan Hladík [ URL "https://kam.mff.cuni.cz/~hladik/"] , Petr Kolman [ URL "ht kam.mff.cuni.cz/~kolman/"] , Andreas E. Feldmann [ URL "https://sites.google.com/site/aefe Raj Tiwary [ URL "https://kam.mff.cuni.cz/~hansraj/"] , Michal Koucký [ URL "https://iuuk. people/koucky.html"] , Martin Koutecký [ URL "http://research.koutecky.name/"] , and Rober "https://iuuk.mff.cuni.cz/people/samal.html"] . *========================================================================================= * Computational complexity *========================================================================================= In the area of computational complexity we study the questions of how efficiently we can s computational problems, how optimal algorithms for various problems look like, what makes solve by a computer, and where is the boundary of what can be solved efficiently. We focus boolean circuits, which is the standard model of computation, on communication complexity, the amount of communication necessary to solve problems by several parties, on extension c is an approach to understanding intractable problems, on limits of efficient data structur achieved outstanding results in the area of lower bounds for various computational models, the relationship between various computational resources, and in extension complexity. We excellent results in the related field of cryptography. Computational complexity and crypt research focus of Michal Koucký [ URL "https://iuuk.mff.cuni.cz/people/koucky.html"] , Zde "https://iuuk.mff.cuni.cz/people/dvorak.html"] , Pavel Hubáček [ URL "https://iuuk.mff.cun hubacek.html"] , and Hans Raj Tiwary [ URL "https://kam.mff.cuni.cz/~hansraj/"] . *========================================================================================= * Knowledge representation *========================================================================================= In representation of knowledge we study problems related to efficient knowledge representa tools of propositional logic, namely using propositional formulas. There are various areas representation, among those we mainly concentrate on knowledge compression and knowledge c In knowledge compression our interest is to find a smallest possible (e.g. in a sense of t formula) representation of given knowledge base. In knowledge compilation we want to trans knowledge base into a form which is suitable for answering particular kinds of queries. On "http://ktiml.mff.cuni.cz/~cepek/"] and Petr Kučera [ URL "http://ktiml.mff.cuni.cz/~kucer principal researchers in this area. *========================================================================================= * Combinatorics and graph theory *========================================================================================= Combinatorics and graph theory models discrete situations, relations and structures, usual only finitely many objects. There are many applications to the society outside of academia modeling large networks but there are also important applications for other sciences such biology. The group has excellent results in structural graph theory, graph and hypergraph Ramsey theory and in intersection of combinatorics and computational complexity. Combinato theory is studied by Jaroslav Nešetřil [ URL "https://iuuk.mff.cuni.cz/people/nesetril.htm Dvořák [ URL "https://iuuk.mff.cuni.cz/people/dvorak.html"] , Robert Šámal [ URL "https:// people/samal.html"] , Martin Loebl [ URL "https://kam.mff.cuni.cz/~loebl/"] , Tereza Klimo "https://iuuk.mff.cuni.cz/~tereza/"] , Jiří Fiala [ URL "https://kam.mff.cuni.cz/~fiala/"] [ URL "https://kam.mff.cuni.cz/~balko/"] , and Jan Hubička [ URL "http://www.ucw.cz/~hubic *========================================================================================= * Discrete and computational geometry *========================================================================================= Geometry is perhaps the oldest branch of mathematics, but discrete and computational geome younger. It is busy with questions on possible configurations of points, lines, curves and with their computational aspects. This problems are also important from the complexity poi group has excellent results on both geometric and topological graphs, in graph drawing, in geometry, in topological methods in combinatorics, in geometric Ramsey theory. Discrete ge topology is the main focus of Pavel Valtr [ URL "https://kam.mff.cuni.cz/~valtr/"] , Jan K "https://kam.mff.cuni.cz/~kyncl/"] , Martin Balko [ URL "https://kam.mff.cuni.cz/~balko/"] Jelínek [ URL "https://iuuk.mff.cuni.cz/people/jelinek.html"] . *========================================================================================= * Hypercubes *========================================================================================= Hypercubes form a class of graphs that is exploited in many applications; it is also an im parallel computers. Today they serve as a tool for modeling of network computers (or users path in hypercube is a Gray code that has applications in many directions, in informationa signal encoding, image processing or data compression. Therefore we orient our research on of hypercubes with special attention to paths covering a hypercube and study of hypercubes vertices. Hypercubes are among research interests of Petr Gregor [ URL "http://ktiml.mff.c and Jiří Fink [ URL "https://ktiml.mff.cuni.cz/~fink/index.html"] . ****************************************************************************************** * Selected outputs ****************************************************************************************** • R. Aharoni, M. Loebl: The Odd Case of Rota's Bases Conjecture. Advances in Mathematics 2 427-442 • M. Balko, J. Cibulka, P. Valtr: Covering Lattice Points by Subspaces and Counting Point- 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 b 38th Annual International Cryptology Conference, Advances in Cryptology - CRYPTO (3) 201 • Z. Dvořák: Thin graph classes and polynomial-time approximation schemes. 29th Annual ACM 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. 45t 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 w Factor in Truly Sub-Quadratic Time. 59th IEEE Annual Symposium on Foundations of Compute 2018: 979-990. Best paper award. • M. Hladík: How to determine basis stability in interval linear programming. Optimization 375-389, 2014. • J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner: Embeddability in the 3-Sphere Is Decidab 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 Packet Deadlines. Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019: 123-14