Výskumné skupiny

Modely výpočtov, zložitosť, algoritmy

V oblasti modelov výpočtov a zložitosti sa v posledných rokoch skúma najmä problematika paralelných gramatík a Turingových strojov, modely komunikácie v mobilných sieťach a skúmanie vplyvu prídavnej informácie na zložitosť riešenia problémov. Boli tiež vyvinuté a implementované algoritmy na transformáciu XML dokumentov, vykresľovanie grafickej reprezentácie štrukturovaných dát a analýzu biologických sekvencií.

Členovia skupiny:

Mgr. Bronislava Brejová, PhD., prof. RNDr. Pavol Ďuriš, CSc., RNDr. Jana Dvořáková, PhD., RNDr. Michal Forišek, RNDr. Jana Katreniaková, PhD., doc. RNDr. Rastislav Královič, PhD., doc. RNDr. Dana Pardubská, PhD., prof. RNDr. Branislav Rovan, PhD., Mgr. Ľuboš Steskal

Vybrané publikácie:

Branislav Rovan, Ľuboš Steskal: Infinite Computations and a Hierarchy in Delta3 Reconsidered. J. Log. Comput. 19(1): 175-176 (2009)
Dana Pardubská, Martin Plátek, Friedrich Otto: On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata. LATA 2009: 660-671
Jakub Kováč, Tomáš Vinař, Broňa Brejová. Predicting Gene Structures from Multiple RT-PCR Tests. WABI 2009: 181-193.
Štefan Dobrev, Rastislav Královič, Dana Pardubská: How Much Information about the Future Is Needed? SOFSEM 2008: 247-258
Peter Gaži, Branislav Rovan: Assisted Problem Solving and Decompositions of Finite Automata. SOFSEM 2008: 292-303
Jiří Wiedermann, Dana Pardubská: Wireless Mobile Computing and its Links to Descriptive Complexity. Int. J. Found. Comput. Sci. 19(4): 887-913 (2008)
Jana Katreniaková: Mental map preserving cluster expansion. SOFSEM (2) 2008: 58-69.
Jana Dvořáková, Filip Zavoral: Xord: An Implementation Framework for Efficient XSLT Processing. IDC 2008: 95-104.
Michal Forišek, Branislav Katreniak, Jana Katreniaková, Rastislav Královič, Richard Kráľovič, Vladimír Koutný, Dana Pardubská, Tomáš Plachetka, Branislav Rovan: Online Bandwidth Allocation. ESA 2007: 546-557.

Kryptológia a informačná bezpečnosť

Hlavné oblasti záujmu sú efektívne a dokázateľne bezpečné konštrukcie kryptografických prvkov, vzťahy a analýza vlastností hašovacích funkcií a bezpečnosť elektronického prostredia (operačné systémy, identifikácia škodlivého kódu a podobne).

Členovia skupiny:

RNDr. Jaroslav Janáček, Mgr. Peter Košinár, doc. RNDr. Daniel Olejár, PhD., RNDr. Richard Ostertág, Mgr. Michal Rjaško, doc. RNDr. Martin Stanek, PhD.

Vybrané publikácie:

Peter Gaži, Martin Stanek: On Ciphertext Undetectability. TATRACRYPT 2007: 133-151.
Richard Ostertág, Martin Stanek: On High-Rate Cryptographic Compression Functions. Computers and Artificial Intelligence 26(1): (2007)
Martin Stanek: Analysis of Fast Blockcipher-Based Hash Functions. ICCSA (3) 2006: 426-435

Diskrétna matematika

V oblasti teórie grafov sa skupina špecializuje na farbenia, najmä hranové farbenia kubických grafov, toky na grafoch, vnáranie grafov do plôch a symetrie grafov. Druhá časť skupiny sa venuje štúdiu booleovských funkcií pomocou kombinatoricko-pravdepodobnostných metód a náhodných grafov a ich aplikácií (napr. komunikácia v sieťach).

Členovia skupiny:

RNDr. Robert Lukoťka, RNDr. Edita Máčajová, PhD., Mgr. Ján Mazák, Mgr. Martin Nehéz, Mgr. Edita Rollová, prof. RNDr. Martin Škoviera, PhD., doc. RNDr. Martin Stanek, PhD., doc. RNDr. Eduard Toman, CSc.

Vybrané publikácie:

Daniel Král, Edita Máčajová, Ondrej Pangrác, André Raspaud, Jean-Sébastien Sereni, Martin Škoviera: Projective, affine, and abelian colorings of cubic graphs. Eur. J. Comb. 30(1): 53-69 (2009)
Gareth A. Jones, Roman Nedela, Martin Škoviera: Complete bipartite graphs with a unique regular embedding. J. Comb. Theory, Ser. B 98(2): 241-248 (2008)
Robert Lukoťka, Martin Škoviera: Real flow number and the cycle rank of a graph. Journal of Graph Theory 59(1): 11-16 (2008)
Ján Mazák: Circular chromatic index of type 1 Blanusa snarks. Journal of Graph Theory 59(2): 89-96 (2008)
Eduard Toman, Daniel Olejár, Martin Stanek: Average degree in the interval graph of a randomboolean function. Computing and Informatics 27(4): 627-638 (2008)
Edita Máčajová, Martin Škoviera: Constructing Hypohamiltonian Snarks with Cyclic Connectivity 5 and 6. Electr. J. Comb. 14(1): (2007)
Daniel Král, Edita Máčajová, Attila Pór, Jean-Sébastien Sereni: Characterization of affine Steiner triple systems and Hall triple systems. Electronic Notes in Discrete Mathematics 29: 17-21 (2007)

Distribuované a paralelné algoritmy

V poslednej dobe sa skupina zameriava na šírenie informácie v prostredí s chybnými linkami, najmä na deterministické modely chýb v sieťach. Ceiľom je navrhovať protokoly, ktoré sú schopné korektne pracovať aj vo veľmi nespoľahlivých prostrediach, aké sa typicky vyskytujú pri senzorových a mobilných sieťach.

Členovia skupiny:

doc. RNDr. Rastislav Královič, PhD., Mgr. Stanislav Miklík, doc. RNDr. Dana Pardubská, PhD., Dr. Tomáš Plachetka

Vybrané publikácie:

Rastislav Královič, Richard Kráľovič: Rapid almost-complete broadcasting in faulty networks. Theor. Comput. Sci. 410(14): 1377-1387 (2009)
Rastislav Královič, Richard Kráľovič: Deterministic Models of Communication Faults. MFCS 2008: 52-67
Štefan Dobrev, Rastislav Královič, Dana Pardubská: Leader Election in Extremely Unreliable Rings and Complete Networks. OPODIS 2008: 512-526
Štefan Dobrev, Rastislav Královič, Richard Kráľovič, Nicola Santoro: On fractional dynamic faults with thresholds. Theor. Comput. Sci. 399(1-2): 101-117 (2008)
Rastislav Královič, Richard Kráľovič: Rapid Almost-Complete Broadcasting in Faulty Networks. SIROCCO 2007: 246-260