semináre v roku 2017

3. 3. 2017, 11:00

Nadia Labai

(TU Wien)

   On the exact learnability of graph parameters: The case of partition functions

We discuss a new direction for research in learning theory and present proof-of-concept. In the exact learning model, the learner can ask the teacher for the value of the target function on some input, or send the teacher a hypothesized function, and have the teacher accept the hypothesis if it is correct, or return a counterexample if it is incorrect. We say a class of functions is exactly learnable if there is a sufficiently fast learner that always finds a correct hypothesis for a function in this class. We review how existing exact learning algorithms exploit certain algebraic properties of their target functions, and suggest developing algorithms for function classes with results of a similar flavor -- in particular, for certain classes of graph parameters. As a first step in this direction, we present an exact learning algorithm for graph parameters which can be represented as a partition function. Examples of such parameters include: the number of independent sets, the number of k-colorings, the number of covering edge sets, and approximations of graph properties.

The talk is about a recent paper with J.A. Makowsky, "On the exact learnability of graph parameters: The case of partition functions", which may be found here: https://arxiv.org/abs/1606.04056

10. 3. 2017, 11:00

Michal Forišek

(KI FMFI UK)

   Rozprávanie o algoritmických súťažiach

Jednou z dobrých foriem rozvoja algoritmického myslenia sú algoritmické súťaže. Za zhruba 50 rokov ich existencie sa veľa zmenilo, zväčša k lepšiemu. Na prednáške si porozprávame trochu o tom, ako to vyzeralo kedysi, ako to vyzerá teraz a kam to bude smerovať v blízkej budúcnosti. Obsah prednášky ešte pochopiteľne v čase písania tohto abstraktu neexistuje, ale môj cieľ je, aby neostalo len pri rozprávaní o tom "ako", ale prišlo aj na čo najviac "prečo". Príďte sa pozrieť, nakoľko sa mi to podarí dosiahnuť.

17. 3. 2017, 11:00

Stefan Dobrev

(MU SAV)

   Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

We consider a well studied problem in adversarial queuing theory, namely routing on directed paths and trees with a single destination, with rate-limited adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, while minimizing the size of the required buffers.

While a centralized algorithm for the problem that uses constant-sized buffers has been recently shown, there is no known local algorithm that achieves a sub-linear buffer size. In fact, greedy algorithms, which have been extensively studied in this setting, have been shown to require buffers of size Theta(n).

In this paper we show tight bounds for the maximum buffer size needed by local algorithms for information gathering on directed paths and trees. We show three main results: 1) a lower bound of O(log n/l) for all l-local algorithms on both directed and undirected paths. 2) a surprisingly simple 1-local algorithm for directed paths that uses buffers of size O(log n) 3) a natural extension of this algorithm to directed trees, achieving the same asymptotic bound. Here, our algorithm is 2-local in order to avoid the simultaneous sending of packets by siblings to a common successor.

Our Omega(log n) lower bound is signiffcantly lower than the Omega(n) lower bound for greedy algorithms; what is perhaps the most surprising is that there is a matching upper bound.



Stefan Dobrev, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny
Submitted to SPAA 2017

24. 3. 2017, 11:00

Juraj Šebej

(UPJŠ)

   Descriptional Complexity of Operations on Formal Languages

We study the state complexity of operations on regular languages. For reversal, we provide a binary worst-case example with a unique final state. Next we prove attainability of all possible values in the range from $log n $ to $2^n$ by the state complexity of the reversal of languages over an alphabet of size $2n$. We also get a segment of a quadratic size of possible values for reversal on languages over a binary alphabet. Then we study the reversal operation on binary prefix-free languages, and provide a lower bound that is smaller than the upper bound just by a constant factor. For star and concatenation, we show attainability of all possible values up to the known upper bounds for languages over an alphabet of size $2n$. We provide the exact complexity of the combined operation of star-complement-star on prefix-free languages over an arbitrary alphabet. Finally, we study Kuratowski algebras generated by prefix-free languages under the operations of star and complementation. We show which of 12 possible algebras can or cannot be generated by prefix-free languages. For algebras generated by a prefix-free language, we also study the state complexities of all generated languages, and we always find a generator that maximizes these complexities.

31. 3. 2017, 11:00

Róbert Lukoťka

(KI FMFI UK)

   Travelling salesman problem on cubic and subcubic graphs

Dvořák, Kráľ, and Mohar [Z. Dvořák, D. Kráľ, B. Mohar: Graphic TSP in cubic graphs, arXiv:1608.07568] proved that every bridgeless simple $2$-connected cubic graph on $n$ vertices with $n_2$ vertices of degree $2$ contains a spanning closed walk of length at most $9/7 cdot n+2/7 cdot n_2 -1$. We provide a significantly shorter proof of this statement. Our analysis of $6$-circuits is sufficiently strong, so that limiting aspect for further improvement is the (lack of) analysis of the $7$-circuits. To demostrate this, we provide a basic analysis to slightly improve the constants in the result of Dvořák, Kráľ, and Mohar. Focusing on circuits of length $6$, we show that a bridgeless cubic graph of girth $6$ has a $2$-factor $F$ that contains $9/13 cdot n$ vertices that are not in $6$-circuits of $F$. The ideas from the proof might provide clues how to further improve the analysis of TSP tours in subcubic graphs.

7. 4. 2017, 11:00

Peter Kostolányi

(KI FMFI UK)

   Bezkontextové gramatiky a analytická kombinatorika

Asymptotické vyčíslenie počtu slov dĺžky n generovaných danou bezkontextovou gramatikou je úloha veľkého významu ako pre enumeratívnu kombinatoriku, tak aj pre teóriu bezkontextových jazykov. Výskum otázok s touto úlohou spojených bol pre jednoznačné gramatiky z veľkej časti zavŕšený nedávnym analyticko-kombinatorickým výsledkom Banderiera a Drmotu charakterizujúcim Puiseuxove rozvoje N-algebraických funkcií. V prvej časti prednášky podáme prehľad vybraných konceptov a tvrdení z oblasti analytickej kombinatoriky s hlavným cieľom priblížiť znenie a myšlienku dôkazu Banderierovej-Drmotovej vety a ozrejmiť jej kľúčové dôsledky.

V rámci druhej časti prednášky odprezentujeme časť originálneho výskumu zameraného na analýzu využívania prepisovacích pravidiel a neterminálov v (nie nutne jednoznačných) bezkontextových gramatikách, ktorý sa o teóriu okolo Banderierovej-Drmotovej vety silno opiera. Hlavnými výsledkami pritom budú charakterizácie bezkontextových gramatík s proporčným využívaním prepisovacích pravidiel resp. neterminálov.

(Prezentované originálne výsledky sú spoločnou prácou s B. Rovanom.)

21. 4. 2017, 11:00

Marek Košta

(UI SAV)

   Real Quantifier Elimination

In this talk I will discuss the problem of real quantifier elimination from both theoretical and practical points of view. I will first formally introduce the problem and shortly discuss its time complexity. Afterwards I will explain the two most prominent practically applicable methods for real quantifier elimination: (1) Cylindrical Algebraic Decomposition and (2) Virtual Substitution. On the way I will briefly mention some of my results on novel concepts for Virtual Substitution. Finally, I will show how concrete problems can be easily solved by the computer logic system Redlog, which implements various methods for real quantifier elimination.

28. 4. 2017, 11:00

Rasťo Královič

(KI FMFI UK)

   Hľadanie pokladu - randomizácia verzus komunikácia.

Budeme sa zaoberať jednoduchým vyhľadávacím problémom: máme nekonečnú postupnosť krabíc očíslovaných prirodzenými číslami. V jednej z nich, x, je ukrytý poklad. Poklad hľadá skupina k hľadačov, pričom nikto z nich nepozná x a každý z nich môže v každom kroku otvoriť jednu krabicu. Zaujíma nás, ako dlho (v závislosti od x) trvá, kým niektorý z hľadačov nájde poklad. Problém začne byť netriviálny, keď pripustíme, že niektorí hľadači môžu zlyhať. Fraigniaud, Korman a Rodeh našli efektívny randomizovaný algoritmus, ktorý nevyžaduje nijakú komunikáciu medzi hľadačmi (takže napr. nevedia zistiť, kto z nich zlyhal). V našom príspevku ukážeme, ako sa situácia zmení, keď randomizáciu vymeníme za veľmi slabú formu komunikácie: ak nejaký hľadač otvorí krabicu, táto už ostane otvorená a ďalší hľadači, ktorí by ju chceli otvoriť neskôr, túto skutočnosť zistia.

spoločná práca so Stefanom Dobrevom a Danou Pardubskou

5. 5. 2017, 11:00

Filip Mišún

(KI FMFI UK)

   Alternating Weighted Automata over Commutatiove Semirings

Budeme sa zaoberať novým rozšírením alternujúcich konečných automatov, v ktorom má každý prechod priradenú váhu z nejakého komutatívneho polokruhu, disjunkcie sú nahradené súčtami a konjunkcie sú nahradené súčinmi. Takto definované automaty nazývame alternujúcimi automatmi s váhami. Alternujúce automaty s váhami realizujú formálne mocninové rady a ich špeciálnym prípadom je aj ďalší dobre známy model - automaty s váhami.

Povieme si o rôznych možných spôsoboch, ktorými možno charakterizovať triedu formálnych mocninových radov realizovaných alternujúcimi automatmi s váhami. Ako hlavný bod programu uvedieme a dokážeme charakterizáciu triedy komutatívnych polokruhov, pre ktoré sú automaty s váhami a alternujúce automaty s váhami rovnako silné. Na záver sa budeme zaoberať uzáverovými vlastnosťami tried radov realizovaných alternujúcimi automatmi s váhami.

19. 5. 2017, 11:00

Stefan Dobrev

(MU SAV)

   Efficient Periodic Traversal on Graphs with Given Rotation Systems

We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The nodes are anonymous, but the ports in each node have unique (within the node) labels. The problem is to design an automaton A and a port re-labeling scheme L such that A performs on L(G) an infinite walk w, periodically visiting all nodes. The goal is to minimize the revisit time (traversal period) pi of w. If L cannot change the input labels, it has been shown by Budach that the problem is unsolvable. If L can in node v use deg(v)+1 labels, it can encode a spanning tree and traversal with period 2n-2 is trivial even with an oblivious agent. The problem is interesting when L is limited to be a permutation. The best known upper bound on the traversal period in such case is 3.5n - 2 by Czyzowicz et al., where n is the number of nodes of G. It is an open problem whether it is possible to achieve traversal period 2n-2. In this paper, we answer this question affirmatively under the assumption that that the input graph G is given with a rotation system. A rotation system of a graph is a combinatorial encoding of graph's embedding into an orientable surface. This encoding can be described by specifying a circular ordering of edges around each node. While this is clearly an additional information, it appears to be barely sufficient to solve the problem with the optimal period 2n-2: Several aspects of the construction need to fit 'just right' to solve all the technical issues, especially in graphs with small maximal degree (3 or 4).

13. 10. 2017, 11:00

Rasťo Královič

(KI FMFI UK)

   Streaming algorithms: old results and new problems

V prednáške predstavíme model prúdových (streaming) algoritmov. Ako príklad uvedieme problém určenia počtu rôznych prvkov: na vstupe je postupnosť n prvkov, pričom každý z nich je z rozsahu 1 až m. Cieľom je zistiť počet rôznych prvkov pomocou algoritmu, ktorý číta vstup iba raz a má pamäť nezávislú od n. Uvedieme klasické výsledky pre deterministické a randomizované algoritmy a predstavíme niekoľko nových pozorovaní a otvorených problémov.

20. 10. 2017, 11:00

Dana Pardubská

(KI FMFI UK)

   One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity

Tomoyuki Yamakami: One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity. DLT 2017

Hlavným výsledkom článku je získanie negatívnej odpovede na otázku (Hromkovič, Schnitger 2010), či jazyk palindrómov možno rozpoznávať pravdepodobnostným zásobníkovým automatom s ohraničenou chybou. Začneme rekapituláciou niektorých starších výsledkov o vzťahu tried bezkontextových jazykov a pravdepodobnostných bezkontextových jazykov s ohraničenou resp. neohraničenou chybou, následne sa sústredíme na použitie Kolmogorovskej zložitosti pri získaní hlavného výsledku článku.

27. 10. 2017, 11:00

Peter Vojtáš

(KFF FMFI UK, Praha)

   Complexity of the search for a Challenge-Response reduction

The idea of reducing (translating) a challenge (question) to another, with the aim of using response (solution, answer) to the latter to obtain response to the former, is a basic and natural one in all areas of human endeavor. We call such a back and forth procedure here “Challenge-Response Reduction (CRR)”. We address particular aspects of CRR in complexity reduction.

3. 11. 2017, 11:00

Mário Lipovský

(KI FMFI UK)

   Approximate Abundance Histograms and Their Use for Genome Size Estimation

DNA sequencing data is typically a large collection of short strings called reads. We can summarize such data by computing a histogram of the number of occurrences of substrings of a fixed length. Such histograms can be used for example to estimate the size of a genome. In this paper, we study a recent tool, Kmerlight, which computes approximate histograms. We discover an approximation bias, and we propose a new, unbiased version of Kmerlight. We also model the distribution of approximation errors and support our theoretical model by experimental data. Finally, we use another tool, CovEst, to compute genome size estimates from approximate histograms. Our results show that although CovEst was designed to work with exact histograms, it can be used with their approximate versions, which can be produced in a much smaller memory.

10. 11. 2017, 11:00

Gabriel Okša

(MÚ SAV)

   Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices.

V prednáške budú prezentované nové výsledky ohľadne gobálnej a asymptotickej kvadratickej konvergencie dvojstranného, paralelného, blokového Jacobiho algoritmu s dynamickým orderingom pre výpočet vlastných čísiel a vektorov Hermitovských matíc.

materiály:

G. Okša, Y. Yamamoto, M. Vajteršic: Asymptotic quadratic convergence of the serial block-Jacobi EVD algorithm for Hermitian matrices, Numer. Math. 136 (2017) 1071-1095, DOI 10.1007/s00211-016-0863-5

G. Okša, Y. Yamamoto, M. Bečka, M. Vajteršic: Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices, 2017, submitted to BIT Numerical Mathematics