Seminár z teoretickej informatiky
Katedra informatiky, FMFI UK

Miestnosť M213 v pavilóne matematiky

28.6.2011 o 14:00     Galina Jirásková (MU SAV Košice) : Self-Verifying Automata and Maximal Cliques in Graphs.

Abstrakt:  Abstract: In self-verifying nondeterminism, computation paths can give three types of answers: yes, no, and I do not know. On each input string, at least one path must give answer yes or no. Furthermore, on the same string, two paths cannot give contradictory answers.

Self-verifying automata are as powerful as deterministic automata; in particular, the standard subset construction can be used to convert them to deterministic automata. Hence, the question arises of investigating this equivalence from the descriptional point of view.

This problem was previously considered by Assent and Seibert (ITA 2007), who proved that each n-state self-verifying automaton can be simulated by a deterministic automaton with O(2^n/sqrt{n}) states.

In the talk, we further deepen this investigation by showing that such an upper bound can be lowered to a function g(n) which grows like 3^{n/3} (we give the *exact* value of the function). In particular, we associate with each n-state self-verifying automaton a certain graph with n vertices, and we prove that there exists a deterministic automaton equivalent to the self-verifying automaton whose state set is isomorphic to the set of the maximal cliques of such a graph. Using a result from graph theory stating the number of possible maximal cliques in a graph (Moon-Moser, Israel J. Math. 1965), we get the upper bound g(n).

The second part of the talk proves the optimality of such an upper bound. We show that for every n, there exists a *binary* language accepted by an n-state self-verifying automaton, such that the minimal equivalent deterministic automaton must have *exactly* g(n) states.


3.6.2011 o 11:00     Burkhard Monien (Universität Paderborn) : Local Search: Simple, Successful, But Sometimes Sluggish.

Abstrakt:  Abstract: In this talk, we survey the research on the complexity of computing locally optimal solutions. We revisit well-known and successful local search heuristics and present results on the complexity of the frequently used standard local search algorithm for various problems. Here, our focus in on worst case, average case, and smoothed complexity along with the existence of sequences of improving steps of exponential length. For a more theoretical investigation, we revisit the framework of and mostly concentrate on the research on Congestion Games, which sparked the interconnection between local search and game theory. We conclude by stating various open problems.

materiál: Burkhard Monien, Dominic Dumrauf a Tobias Tscheuschner: Local Search: Simple, Successful, But Sometimes Sluggish, ICALP, 2010


27.5.2011 o 11:00     Dan Kráľ (MFF UK) : Algorithms for testing FOL properties.

Abstrakt:  Abstract: In 2001, Frick and Grohe showed that every FOL property, a property expressable in first order logic, can be tested in almost linear time in graph classes with locally bounded tree-width. Such graph classes include planar graphs or graphs with bounded maximum degree. An example of an FOL property is the existence of a fixed graph as a subgraph.

We generalize this result in two directions:



20.5.2011 o 11:00     Michal Forišek (KI FMFI) : Výpočtová zložitosť vybraných hier pre jedného hráča.

Abstrakt:  Abstract: Rôzne hry a hlavolamy pre jedného hráča (napr. sokoban, tetris, sudoku) už boli skúmané z hľadiska výpočtovej zložitosti riešenia, zväčša s výsledkom, že nájdenie optimálneho riešenia (a často aj dostatočne dobrej aproximácie) je NP-tažké alebo ešte tažšie.

Na seminári budem rozprávať niečo stručne o tom, prečo sa takýto výskum vôbec oplatí robiť. Ďalej ukážem niektoré konkrétne vlastné výsledky o výpočtovej zložitosti hier (týkajúce sa napr. hier Lemmings a Prince of Persia) a na záver uvediem niekoľko otvorených problémov, ktoré by mali byť zmysluplne riešitelné.


13.5.2011 o 11:00     Monika Steinová (ETH) : Improved Approximations for TSP with Simple Precedence Constraints

Abstrakt:  Abstract: In this talk, we consider variants of the traveling salesman problem with precedence constraints. We characterize hard input instances for Christofides' algorithm and Hoogeveen's algorithm by relating the two underlying problems, i.e., the traveling salesman problem and the problem of finding a minimum-weight Hamiltonian path between two prespecified vertices. Furthermore, we improved algorithms for the ordered TSP (i.e., the TSP, where the precedence constraints are such that a given subset of vertices has to be visited in some prescribed linear order.). For near-metric input instances satisfying a relaxed triangle inequality, we improve the best previously known approximation ratio to k\beta^{\log_2 (3k-3)} and for the metric case, we present an algorithm that guarantees an approximation ratio of 2.5 - 2/k (in both ratios k is the number of ordered vertices).

materiál: Hans-Joachim Böckenhauer, Ralf Klasing, Tobias Mömke, Monika Steinova: Improved Approximations for TSP with Simple Precedence Constraints , CIAC, 2010


29.4.2011 o 11:00     Petr Jančár (FEI VŠB-TU Ostrava) : A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars

Abstrakt:  Abstract: The main aim of the talk is to give a short self-contained proof of the decidability of language equivalence for deterministic pushdown automata, which is the famous problem solved by G. Senizergues, for which C. Stirling has derived a primitive recursive complexity upper bound. The proof here is given in the framework of first-order grammars, which seems to be particularly apt for the aim.


15.4.2011 o 11:00     Ivo Kováč (KI FMFI UK) : Balanced Use of Resources: The Equiloaded Automata Case

Abstrakt:  Abstract: In the paper presented we initiate the study of a balanced use of resources in sequential computations. We consider a particular model of computation -- deterministic finite automaton, and take states as the resource to be used in a balanced way. In this setting we develop notions and prove results which can serve as an example for similar studies in other settings. We present two possible approaches to define an equiloaded finite automaton and we analyze corresponding families of automata and languages.


1.4.2011 o 11:00     Janka Katreniaková (KI FMFI UK) : Edge routing and bundling for graphs with fixed node positions .

Abstrakt:  In some graph drawing scenarios, the positions of the nodes are already defined and cannot be modified (for example, they were provided by the user) and the graph drawing techniques are only used to draw edges between the nodes. The number of nodes in such cases tends to be relatively small (tens or hundreds of nodes at most) however the users want to see all of the edges. Various edge routing techniques can provide such services, but if the graph is dense, the drawing can get rather hard to read due to the high number of lines required to visualize the edges. In such cases, clarity can be improved by bundling individual edges (more precisely parts of their drawing) into larger groups and draw as a single line. In this paper, we provide several different techniques for edge bundling based on an edge routing algorithm, compare and evaluate them.

Spoločná práca s J. Dokulilom


11.3.2011 o 11:00     Pavel Labath (KI FMFI UK) : Zjednodušenie DPDA prídavnou informáciou.

Abstrakt:  V práci skúmame vplyv prídavnej informácie na zložitosť automatov rozpoznávajúcich nejaké jazyky. "Prídavná informácia" znamená to, že automatu dovolíme predpokladať, že vstup patrí do nejakého poradného jazyka. V práci skúmame jazyky rozpoznávané deterministickými zásobníkovými automatmi s regulárnym poradným jazykom. V prvej časti sa zaoberáme deterministickými bezkontextovými jazykmi z pohľadu zložitosti. Skúmame rôzne spôsoby definovania zložitosti zásobníkových automatov a jazykov ktoré rozpoznávajú, hľadáme tesné odhady zložitosti niektorých tried jazykov a ukazujeme konštrukciu normálneho tvaru "automat vždy dočíta vstup", ktorá nevyžaduje pridanie exponenciálneho počtu stavov. V druhej časti využívame tieto poznatky na skúmanie vplyvu regulárnej prídavnej informácie na zložitosť. Dokazujeme existenciu nekonečnej podtriedy deterministických zásobníkových jazykov, pre ktoré vhodná regulárna prídavná informácia umožní zjednodušiť deterministický zásobníkový automat pre ich akceptovanie. Dokážeme aj existenciu nekonečnej triedy deterministických bezkontextových jazykov, obsahujúcej ľubovoľne zložité jazyky, pri ktorých žiadna regulárna prídavná informácia neumožní znížiť zložitosť deterministického zásobníkového automatu pre ich akceptovanie.

materiál: P. Labath, B. Rovan: Simplifying DPDA Using Supplementary Information , LATA, 2011


4.3.2011 o 11:00     Rasťo Královič (KI FMFI UK) : Online algoritmy s vysokou pravdepodobnosťou.

Abstrakt:  Seminár bude prezentovať prebiehajúci výskum v oblasti randomizovaných online algoritmov. Pod randomizovaným online algoritmom rozumieme algoritmus, ktorý využíva zdroj náhodných bitov, a teda ktorého výstup je náhodná premenná. Pre analýzu kvality algoritmu sú najdôležitejšími parametrami stredná hodnota výstupu a jeho disperzia. Jednoduchým spôsobom, ako znížiť disperziu je nezávisle niekoľkokrát zopakovať beh algoritmu na rovnakom vstupe. Pri online problémoch sa vyžaduje inkrementálne spracovanie vstupu: časť výstupu musí byť zafixovaná skôr, ako je známy celý vstup, preto nie je možné viacnásobné spustenie. Zaujíma nás, za akých podmienok vieme z existencie algoritmu s danou strednou hodnotou C odvodiť existenciu algoritmu, ktorý dosahuje cenu (1+e)C s veľkou pravdepodobnosťou.


7.1.2011 o 11:00     David Pal (University of Alberta) : Online learning

Abstrakt:  Online učenie (online learning) je podoblasť strojového učenia, kde učiaci algoritmus v každom kole vykoná nejakú akciu, príjme spätnú väzbu a pripíše si nejakú stratu/zisk. Úlohou algoritmu je mať zisk/stratu porovnateľne dobrú ako nejaká množina stratégií. Online učenie má mnoho praktických aplikácií od finančníctva, cez internetovú reklamu, a spracovanie masívnych dát. Z matematického hľadiska má online učenie prepojenie na klasické online algoritmy, teóriu (opakovaných) hier, numerickú optimalizáciu (napr. gradient descent) a teóriu pravdepobnosti. Seminár bude prehľad oblasti. Predstavím zopár klasických problémov (mnohoruký bandita, učenie sa z rád expertov, online klasifikácia).

2010



17.12.2010 o 11:00     Dana Pardubská (KI FMFI UK) : Factoring and Testing Primes in Small Space

Abstrakt:  We discuss how much space is required to decide whether a unary number~n is a prime. We show that O(loglog n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. That is, un-Primes is in pebble-DSPACE(loglog n) and also in accept-ASPACE(loglog n), where un-Primes={1^n : n is a prime}. Moreover, if the given n is composite, such machines are able to find a divisor of~n. Since O(loglog n) space is too small to write down a divisor which might require Omega(log n) bits, the witness divisor is indicated by the input head position at the moment when the machine halts.

materiál: V. Geffert, D. Pardubská: Factoring and Testing Primes in Small Space , SOFSEM, 2009


3.12.2010 o 11:00     Richard Štefanec (KI FMFI UK) : Vzťah deterministických a nedeterministických dvojsmerných automatov

Abstrakt:  V tomto príspevku predstavíme niekoľko klasických výsledkov z oblasti venujúcej sa stavovej zložitosti dvojsmerných automatov. Predstavíme problémy Two-way liveness a One-way liveness, ktoré sú úplne vzhľadom k otázke, či ku každému dvojsmernému (resp. jednosmernému) nedeterministickému automatu, existuje ekvivalentný dvojsmerný deterministický automat s nanajvýš polynomiálne vyšším počtom stavov. Zároveň uvedieme niekoľko výsledkov týkajúcich sa vzťahu spomenutých automatov a tzv. sweeping automatov -- dvojsmerných automatov, ktoré môžu zmeniť smer len na koncoch slova.


19.11.2010 o 11:00     Rasťo Královič (KI FMFI UK) : On the Advice Complexity of the k-Server Problem

Abstrakt:  Kompetitívna analýza je štandardný spôsob vyhodnocovania efektivity online algoritmov. Nedávno sme predstavili nový koncept "advice complexity" (informačná zložitosť), ktorá meria efektivitu online algoritmov pri pridaní globálnej informácie o vstupe. Zaujíma nás, koľko informácie je potrebné na dosiahnutie optimálneho riešenia a ako závisí kvalita riešenia od množstva pridanej informácie.

Predstavíme nové horné a dolné odhady na informačnú zložitosť k-server problému a všeobecné výsledky o vzťahu pridanej informácie a randomizácie.


5.11.2010 o 11:00     Branislav Rovan (KI FMFI UK) : Zamyslenie nad pojmom informácia

Abstrakt:  The formalisation of the notion of information we use was introduced over half a century ago by Shannon in order to study problems in transmitting information. More adequate formalisation is needed to capture and study new ways of using and processing information. We shall mention some attempts in this direction that are beginning to emerge. We shall briefly discuss several attributes of information and concentrate on a particular formalisation for measuring usefulness of information.


7.5.2010 o 11:00     Matej Lexa (MU Brno) : Software a hardware pre identifikáciu sekvencií DNA podporujúcich alternatívne sekundárne štruktúry

Abstrakt:  V súvislosti s našou rastúcou schopnosťou produkovať sekvencie DNA narastá aj potreba analyzovať ich obsah. Okrem identifikácie kódujúcich oblastí, ktoré napr. v ľudskom genóme zaberajú iba niekoľko percent genómu, je aktuálna aj identifikácia vzorov, ktoré by mohli mať iné biologické funkcie. Zaujímajú nás sekvencie schopné vytvárať alternatívne usporiadania nukleotidov v priestore (napr. krížová a triplexová DNA), pretože sa predpokladá ich účasť na regulácii génov. Ich funkcia by mohla spočívať v uľahčení alebo naopak sťažení väzieb DNA-proteín, regulácii transkripcie či modulovaní stavu DNA a chromatínu v danej oblasti genómu. Predstavím krížovú a triplexovú DNA a algoritmy, ktoré umožňujú efektívne nájsť sekvencie kompatibilné s týmito štruktúrami. Uvediem príklady paralelizácie výpočtov pomocou hradlových polí (FPGA).


16.4.2010 o 11:00     Martin Nehéz (VŠM) : Fázový prechod dominujúcich klík v náhodných grafoch

Abstrakt:  Problém dominujúcich klík v Erdosovom-Renyiho modeli náhodných grafov G(n,p) je motivovaný intervalovým smerovaním na náhodných grafoch. Ukážeme, že tento problém má fázový prechod s dvoma krajnými hodnotami pravedopodobnosti p: $(3 - \sqrt{5})/2$ a $1/2$. Ukážeme tiež, že hodnoty fázového prechodu závisia od veľkosti klík v náhodných grafoch. Podrobné preskúmanie tejto závislosti má význam pri riešení otázky, či je naše určenie hodnôt fázového prechodu najlepšie možné. Pri riešení tejto otázky sme použili aj počítačové simulácie, ktoré potvrdzujú dokázané výsledky.

Spoločná práca s D. Olejárom a M. Demetrianom


19.3.2010 o 11:00     Pavol Černý (Institute of Science and Technology Austria) : Single-Pass List Processing Algorithms as MSO-Definable Transducers

Abstrakt:  Two-way deterministic finite-state transducers define the class of ``regular'' transductions -- (partial) functions from input words to output words, which also has a logical MSO-based characterization. We introduce a new kind of a transducer, heap-based (deterministic) transducer, that reads the input word from left to right in a single pass, and computes the output using a heap of cells storing output symbols and connected by {\em next\/} pointers. Using a finite number of pointer variables ranging over the heap cells, the transducer can dynamically update the heap structure by adding new cells and changing next-pointers.

We prove that our model is expressively equivalent to the classical two-way model. We also establish Pspace bounds for the problems of checking equivalence of two heap-based transducers, and of checking whether a heap-based transducer satisfies pre/post verification conditions specified by automata over input/output words.

Spoločná práca s Rajeev Alur


5.3.2010 o 11:00     Stanislav Miklík (KI FMFI UK) : Periodic Data Retrieval Problem in Rings Containing a Malicious Host

Abstrakt:  In the problems of exploration of faulty graphs, a team of cooperating agents is considered moving in a network containing one or more nodes that can harm the agents. A most notable among these problems is the problem of black hole location, where the network contains one node that destroys any incoming agent, and the task of the agents is to determine the location of this node. The main complexity measure is the number of agents needed to solve the problem. In this paper we begin with a study of malicious hosts with more varied behavior. We study the problem of periodic data retrieval which is equivalent to periodic exploration in fault-free networks, and to black hole location in networks with one black hole. The main result of the paper states that, in case of rings, it is sufficient to protect the internal state of the agent (i.e. the malicious host cannot change or create the content of agent’s memory), and the periodic data retrieval problem is solvable by a constant number of agents.

Spoločná práca s Rasťom Královičom.


26.2.2010 o 11:00     Jiří Wiedermann (Ústav informatiky AV ČR) : Výpočty coby neohraničené procesy.

Abstrakt:  Na semináři budeme referovat o průběžných výsledcích spolupráce autora s J. van Leeuwenem (Utrechtská univerzita), zaměřené na takové rozšíření pojmu vypočítatelnosti, které by odpovídalo našemu současnému chápání pojmu výpočtů. Budeme se zabývat novým turingovským modelem výpočtu, který zachycuje výpočet jako časově neohraničený proces. Složitost výpočtu bude měřena počtem pozorovatelných změn (tzv. revokací) chování výpočetního zařízení během výpočtu. Model opouští klasické paradigma konečných výpočtů a sjednocuje několik dříve zavedených koncepcí, jako jsou relativistické výpočty, výpočty metodou pokusů a omylů či tzv. limitní rekurze. Model prakticky posouvá hranice efektivních výpočtů na druhou úroveň aritmetické hierarchie - model akceptuje \Delta_2 jazyky a rozeznává \Sigma_2 jazyky. Nedeterministická verze modelu umožňuje definovat jistou vzdálenou analogii klasického P vs. NP problému. Ukážeme, že pro jisté rozumně omezené třídy výpočtů je nedeterministická verze modelu dokazatelně silnější než jeho deterministická verze, vzhledem k polynomiálně ohraničenému počtu revokací.


19.2.2010 o 11:00     Tomáš Kulich (KI FMFI UK) : Incompressibility method and Lovasz Local Lemma .

Abstrakt:  Schweitzer [Inform. Process. Lett. 109 (2009), 229-232] described a connection between the incompressibility method and the Lov\' asz Local Lemma. The idea was illustrated on the problem of estimating van der Waerden numbers. Sadly, there is an inaccuracy in the above mentioned paper which lies in the use of a non-injective coding. We present an easy fix to make the coding injective without loss of strength. Furthermore, we show that the coding we use is in some sense the best possible and that better results can not be obtained by using the same approach.

2009



4.12.2009 o 11:00     Janka Katreniaková (KI FMFI UK) : Using Clusters in RDF Visualization.

Abstrakt:  Clustered graph visualization techniques are an easy to understand way of hiding complex parts of a visualized graph when they are not needed by the user. When visualizing RDF, there are several situations where such clusters are defined in a very natural way. Using this techniques, we can give the user optional access to some detailed information without unnecessarily occupying space in the basic view of the data. This paper describes algorithms for clustered visualization used in the Trisolda RDF visualizer.

materiál: J. Dokulil, J. Katreniaková: Using Clusters in RDF Visualization , SEMAPRO, 2009


20.11.2009 o 11:00     Tomáš Plachetka (KI FMFI UK) : Grupovanie a agregácia v relačných databázach.

Abstrakt:  Vysvetlíme, čomu zodpovedá SQL-ovská agregácia (GROUP BY/SUM/COUNT/...) v relačnom (predikátovom) kalkule a v Datalogu, resp. Prologu. Predvedieme návrh "čistého" rozhrania a algoritmus výpočtu univerzálneho subtotalu v Prologu. Algoritmus je zaujímavý neobvyklým použitím vnorenej rekurzie.


13.11.2009 o 11:00     Tomáš Záthurecky (KI FMFI UK) : Rozlišovanie susedov v nepravidelných a asynchrónnych bunkových automatoch so stromovými prepojeniami.

Abstrakt:  Nepravidelný a asynchrónny bunkový automat je výpočtové zariadenie, ktoré sa skladá z mnohých rovnako naprogramovaných konečných automatov (buniek), ktoré sú navzájom poprepájané a môžu komunikovať. Nepravidelnosť znamená, že bunka nepozná presnú štruktúru prepojení a pritom chceme, aby celé zariadenie fungovalo správne pre každé prepojenie spĺňajúce isté podmienky. Podobme asynchrónnosť znamená, že chceme, aby zariadenie fungovalo správne pre každé časovanie spĺňajúce isté podmienky. Keďže jednotlivé bunky sú na začiatku rovnaké, je užitočné nájsť spôsob, ako ich rozlíšiť. Ukážeme si, ako môžu bunky rozlíšiť svojich susedov v prípade, že prepojenia buniek sú zakorenené stromy (dostatočne nesymetrické).


16.10.2009 o 11:15     Matúš Mihaľák (KI FMFI UK) : Ako strážiť graf?

Abstrakt:  V tomto príspevku iniciujeme štúdium algoritmických základov hier na grafoch v ktorých množina policajtov stráži určenú oblasť v grafe pred zlodejom. Policajti a zlodej sú na začiatku umiestnení na vrcholoch grafu a potom sa striedajú v ťahoch: v každom ťahu sa môže každý policajt (alebo zlodej) presunúť na susedný vrchol. Cieľ zlodeja je vstúpiť na vrchol stráženej oblasti na ktorom nie je policajt. Problém ktorý študujeme je nájsť minimum policajtov ktorí zamedzia vstupeniu zlodeja na nechranený vrchol stráženej oblasti. Tento problém je netriviálny už keď sa zameriame na veľmi jedoduché oblasti. Napríklad, ak oblasť v ktorej sa zlodej pohybuje predtým než vstúpi na chránenú oblasť je cesta v grafe, problém sa dá vyriešiť v polynomiálnom čase. Na druhú stranu, ak táto oblasť je strom, potom rozhodovacia verzia je NP-úplný problém. Navyše, ak sa zlodej pohybuje v orientovanom acyklickom grafe, problém je PSPACE-úplný.

materiál: RF. V. Fomin, P. A. Golovach, A. Hall, M. Mihalak, E. Vicari, P. Widmayer: How to Guard a Graph? , ISAAC, 2008


15.5.2009 o 11:00     Broňa Brejová (KI FMFI UK) : On-line Viterbiho algoritmus a jeho analýza

Abstrakt:  Skryté Markovove modely (HMM) sa často používajú v bioinformatike na rozpoznávanie rôznych prvkov v DNA sekvenciách, ako sú gény, CpG ostrovy a evolučne konzervované oblasti. Klasický Viterbiho algoritmus pre HMM používa pamäť Theta(mn) na analýzu postupnosti dĺžky n s m-stavovým modelom, čo je nepraktické, ak analyzujeme dlhé postupnosti, napríklad celé chromozómy. Na tomto seminári predstavíme on-line Viterbiho algoritmus, ktorý používa oveľa menšiu pamäť. Ukážeme, že pre dvojstavové modely je priemerná pamäť Theta(mlogn) a tento odhad sa dá rozšíriť aj na niektoré viacstavové modely. Naopak, pre niektoré modely algoritmus potrebuje Omega(n) pamäť a pre ďalšie skupiny modelov je ich priemerná pamäťová zložitosť zatiaľ otvorená.

materiál: Rasťo Šrámek, Broňa Brejová, Tomáš Vinař, Uri Keich: On-Line Viterbi Algorithm for Analysis of Long Biological Sequences. , WABI, 2007


24.4.2009 o 11:00     Martin Mačaj (KAGDM FMFI UK) : Prečo a ako riešiť rovnicu x2 + bx + c = 0

Abstrakt:  Ukážeme triedu kombinatorických problémov, ktoré sa dajú previesť na hľadanie riešení kvadratickej rovnice v triede matíc s nezápornými celočíselnými koeficientami. Ďalej sa zamyslíme nad problémami, ktoré sa môžu vyskytnúť pri hľadaní riešení pomocou počítača.


3.4.2009 o 11:00     Mirka Kemeňová (KI FMFI UK) : Restricting the resources in generation of infinite words.

Abstrakt:  We present various ways to generate one-way infinite words in real time. The most used methods are based on iterative application of a morphism (or other mappings) onto a single letter. We show a unifying approach to these generating machinery via AG-systems.

Next, we prove that iteration of a deterministic generalized sequence machine (GSM) creates an infinite dense hierarchy, depending on number of states used in the generation of an infinite words. We show that a similar result holds also for a class of words generated as a coding of a product of iterating a simple morphism.


13.3.2009 o 11:00     Stano Miklík (KI FMFI UK) : On Multiple Black Holes.

Abstrakt:  In this talk we consider a set of mobile agents operating in a networked environment. Some of the nodes, called black holes, are harmful, and destroy all incoming agents without any observable trace. While the network topology is known to the agents, the locations of the black holes are not. In the black hole search problem, the agents have to cooperate in determining the locations of all black holes. The question is how many agents are required to solve the problem, and also how many moves, cumulative for all agents, are needed to locate all black holes with the minimum possible number of agents.

Using the assumption that the number of black holes k is strictly less than the vertex connectivity of the graph we show that there exists a generic protocol for arbitrary graphs using k+1 agents and O(k^3n\log n) moves. We further show that for hypercubes the number of moves is O(n), and does not depend on k. Finally, we show that relaxing the assumption about connectivity leads to \Theta(n^2) solution in general.


27.2.2009 o 11:00     Mišo Foríšek (KI FMFI UK) : Teoretické aspekty ratingových algoritmov.

Abstrakt:  Zaoberáme sa situáciami, v ktorých sa množina subjektov pravidelne zúčastňuje súťaží. Výstupom každej súťaže je objektívne merané poradie. Ratingový algoritmus je algoritmus, ktorý na základe týchto výsledkov spočíta číselné ohodnotenie subjektov odzrkadľujúce mieru ich schopnosti. Moderné ratingové systémy (TrueSkill, TopCoder) sú založené na Bayesovskom uvažovaní.

V našej práci analyzujeme novú možnosť návrhu ratingových systémov, založenú na Item Response Theory. Tento prístup nám pomôže získať presnejšie informácie v situáciách, kedy rôzne kolá súťaže nie sú rovnocenné, napr. sa líšia obtiažnosťou úloh. Definujeme spôsob ako je možné objektívne porovnávať ratingové systémy.

Ďalej analyzujeme existujúce ratingové systémy z hľadiska bezpečnosti. Ukažuje sa, že pri ich návrhu sa s možnosťou útoku vôbec nerátalo. Ukážeme niekoľko útokov voči existujúcim ratingovým systémom. (Útok v tomto prípade znamená, že zanedbateľne malá skupina dokáže systém oklamať, najčastejšie teda zvýšením ratingu niektorého člena skupiny nad úroveň zodpovedajúcu jeho schopnostiam.)


13.2.2009 o 11:00     Janka Dvořáková (MFF UK Praha) : Using Input Buffers for Streaming XSLT Processing

Abstrakt:  We present a buffering streaming engine for processing top-down XSLT transformations. It consists of an analyzer and a transformer. The analyzer examines given top-down XSLT and XSD, and generates fragments which identify parts of XSD need to be buffered when XSLT is applied. The fragments are passed to the transformer which processes XSLT on an input XML document conforming to XSD. It uses auxiliary memory buffers to store temporary data and buffering is controlled according to the fragments. We describe implementation of the engine within the Xord framework and provide evaluation tests which show that the new engine is much more memory-efficient comparing to the common XSLT processors.


12.2.2009 o 15:00     Euripides Markou (University of Central Greece) : Connectivity in ad-hoc networks with selfish nodes

Abstrakt:  Inspired by the CONFIDANT protocol (S. Buchegger and J.-Y. Le Boudec, MOBIHOC'02), we define and study a basic reputation-based protocol in multihop wireless networks with selfish nodes. Its reputation mechanism is implemented through the ability of any node to define a threshold of tolerance for any of its neighbors, and to cut the connection to any of these neighbors that refuse to forward an amount of flow above that threshold. The main question we would like to address is whether one can get the initial conditions so that the system reaches an equilibrium state where a non-zero amount of every commodity is routed. This is important in emergency situations, where all nodes need to be able to communicate even with a small bandwidth. Following a standard approach, we model this protocol as a game, and we give necessary and sufficient conditions for the existence of non-trivial Nash equilibria. Then we enhance these conditions with extra conditions that give a set of necessary and sufficient conditions for the existence of connected Nash equilibria. We note that it is not always necessary for all the flow originating at a node to reach its destination at equilibrium. For example, a node may be using unsuccessful flow in order to effect changes in a distant part of the network that will prove quite beneficial to it. We show that we can decide in polynomial time whether there exists a (connected) equilibrium without unsuccessful flows. In that case we calculate (in polynomial time) initial values that impose such an equilibrium on the network. On the negative side, we prove that it is NP-hard to decide whether a connected equilibrium exists in general (i.e., with some nodes using unsuccessful flows at equilibrium).

materiál: George Karakostas and Euripides Markou: Emergency connectivity in ad-hoc networks with selfish nodes. , LATIN, 2008


12.1.2009 o 11:00     Pavol Cerny (University of Pennsylvania) : Algoritmická analýza programov s poliami

Abstrakt:  Pre programy, ktoré majú len Boolovské premenné, je problém dosiahnuteľnosti rozhodnuteľný (PSPACE-úplný). Na tomto fakte sú založené mnohé často používané verifikačné programy. V mojom príspevku sa budem zaoberať programami, ktoré majú Boolovské premenné, ale aj premenné nad (nekonečnou) doménou D, ako aj pole, ktorého dĺžka je neohraničená, a ktorého prvky sú z domény D. Hlavným obmedzením je, že nad doménou D máme iba testy na rovnosť a usporiadanie. Problémy, ktorých riešenia môžeme programovať v tomto fragmente zahŕňajú vyhľadávanie a triedenie.

Ukážeme, že problém dosiahnuteľnosti je: 1) PSPACE-úplný pre programy bez vnorených cyklov, 2) v EXPSPACE pre programy s ľubovolne vnorenými cyklami ak uvažujeme len konečnú doménu D, 3) rozhodnuteľný pre istú triedu programov s dvojito-vnorenými cyklami. Tento výsledok ukáže súvislosti medzi programami na jednej strane a automatmi a logikou nad dátovými slovami (data words) na druhej strane.


9.1.2009 o 11:00     David Pal (Waterloo) : Showing Relevant Ads via Context Multi-Armed Bandits.

Abstrakt:  We study context multi-armed bandit problems where the context comes from a metric space and the payoff satisfies a Lipschitz condition with respect to the metric. Abstractly, a context multi-armed bandit problem models a situation in which, in a sequence of independent trials, an online algorithm chooses an action based on a given context (side information) from a set of possible actions so as to maximize the total payoff of the chosen actions. The payoff depends on both the action chosen and the context. In contrast, context-free multi-armed bandit problems, studied previously, model situations where no side information is available and the payoff depends only on the action chosen.

For concreteness we focus in this paper on an application to Internet search advertisement where the task is to display ads to a user of a Internet search engine based on his search query so as to maximize the click-trough rate of the ads displayed. We cast this problem as a context multi-armed bandit problem where queries and ads form metric spaces and the payoff function is Lipschitz with respect to both the metrics. We present an algorithm, give upper bound on its regret and show an (almost) matching lower bound on the regret of any algorithm.

Spoločná práca s Tyler Lu a Martinom Palom.

2008



12.11.2008 o 9:00     Martin Macko (FMFI UK) : Hry so zahltením - modifikácia KP modelu a FMNE hypotéza.

Abstrakt:  Hry so zahltením na sieťach sú klasickým konceptom algoritmickej teórie hier. Tieto hry modelujú správanie sebeckých užívateľov zahltených sietí a ich stratégie, ako budú routovať svoje dáta v sieti. Definujeme klasický KP model hry so zahltením na sieti, ktorá sa skladá iba z dvoch vrcholov -- zdroj a cieľ dát -- a niekoľkých paralelných liniek spájajúcich tieto vrcholy, a jeho modifikáciu s upravenou globálnou účelovou funkciou vyjadrujúcou spoločenské náklady stratégie. Upravená spoločenská funkcia bude namiesto maximálneho zahltenia linky brať do úvahy súčty štvorcov zahltení na všetkých linkách.

Pre modifikovaný KP model sformulujeme FMNE (Fully Mixed Nash Equilibrium) hypotézy vyslovenej pre klasický KP model a ukážeme niektoré jej vlastnosti.


14.11.2008 o 11:00     Tomáš Záthurecký (FMFI UK) : Nepravidelné a asynchrónne bunkové automaty s dvojrozmernými prepojeniami.

Abstrakt:  Definujeme zovšeobecnenú verziu bunkových automatov, ktoré umožňujú mať aj nepravidelné prepojenia buniek a asynchrónne časovanie výpočtu. Definujeme spôsob ich práce, v ktorom jednotlivé bunky nepoznajú presné detaiy ich vzájomného prepojenia a časovania. Takýto výpočtový model dokáže simuovať Turingov stroj, ale len s exponenciálnym zhoršením priestorovej zožitosti. Definujeme triedu dvojrozmerne vyzerajúcich prepojení a ukážeme, že na takýchto prepojeniach náš výpočtový model dokáže simulovať Turingov stroj bez zhoršenia zložitosti.


7.11.2008 o 11:00     Dana Pardubská (FMFI UK) : Parallel Communicating Grammar Systems and Analysis by Reduction by Restarting Automata.

Abstrakt:  We study the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restrating Automata (FRR). We show that analysis by reduction for a PCGS with m components and with communication complexity bounded by constant k can be implemented by a strongly linearized deterministic FRR-automaton with t rewrites per cycle; this implementation is almost optimal. As a consequence we obtain a pumping lemma for the class of languages generated by PCGS with constant communication complexity and the fact, that this class of languages is semi-linear.

materiál: Dana Pardubská, Martin Plátek: Parallel Communicating Grammar Systems and Analysis by reduction by Restarting Automata. , ForLing, 2008


24.10.2008 o 11:00     Ľuboš Steskal (FMFI UK) : Minimum Description Length a klasifikácia pľúcnych ochorení

Abstrakt:  Predstavíme si Minimum Description Length principle (MDL) - metódu štatistického učenia bez učiteľa, ktorej v istom zmysle limitným prípadom je Kolmogorovská zložitosť. Základnou myšlienkou je úvaha, že najlepší model popisujúci dáta je taký, v ktorom je dĺžka popisu dát a samotného modelu minimálna; teda model, ktorý celkom dobre popisuje dáta ale zároveň nie je "príliš naviazaný" na dáta, ktoré máme (teda nedochádza k preučeniu). Porovnáme MDL s metódou maximálnej vierohodnosti.

Ďalej ukážeme príklad použitia pri klasifikácii fajčiarskych ochorení pľúc. Na sade CT snímkov sa vytvorí clustrovanie jednotlivých pixlov. Klasifikácia sa uskutoční na základe príslušnosti do jednotlivých clustrov. Pre výber najlepšieho clustrovania sa použije princíp MDL.


17.10.2008 o 11:00     Martin Nehez (VŠM) : Renormalizácia bezškálových sietí

Abstrakt:  Model bezškálových sietí sa vyznačuje mocninovým rozdelením stupnov vrcholov a súčasne predstavuje typ sietí, aké sa často vyskytujú v reálnom svete (napr. elektrická rozvodná sieť, Internet, sieť web-stránok, sociálne siete, ...). Z matematického hľadiska je renormalizácia prechod od diskrétnych bodov spočitateľnej množiny ku kontinuu. Jej aplikácie sú známe najmä vo fyzike (kvantová teória poľa, statistická mechanika). V prípade bezškálových sietí sa renormalizácia dá chápať ako aplikovanie nejakej grafovej transformácie, ktoraá zachováva vlastnosť bezškálovosti ako invariant.

My sa budeme zaoberať renormalizáciou bezškálových sietí z algoritmického hľadiska. Ukážeme, že tento problém patrí medzi algoritmicky "ťažké" a navrhneme heuristiku, ktorá rieši problém iterovanej renormalizácie. Uvedieme tiež experimentálne vyhodnotenie uvedenej heurisitky, ako aj aplikácie v oblasti návrhu pamäťovo-efektívnej repreznetácie bezškálových sietí.


3.10.2008 o 11:00     Rasťo Královič (FMFI UK ) : Kedy sa vyplatí krištáľová guľa alebo ako pomáha informácia o budúcnosti (správa z cesty)

Abstrakt:  Neformálne porozprávam o rozpracovaných výsledkoch z augustového pobytu v Zurichu. Zaoberáme sa online algoritmami, t.j. algoritmami, ktoré spracovávajú vstup inkrementálne. Kvalita riešenia (competitive ratio) sa meria porovnaním s optimálnym algoritmom poznajúcim celý vstup. V našom modeli môže online algoritmus pred začiatkom výpočtu na (neznámom) vstupe x zistiť hodnotu f(x), kde f je ľubovoľná funkcia. Zaujíma nás vzťah veľkosti (počtu bitov) f(x) na kvalitu dosiahnutého riešenia.


30.5.2008 o 11:00     Stefan Dobrev (MU SAV ) : The Power of Tokens: Rendezvous and Symmetry Detection for two Mobile Agents in a Ring

Abstrakt:  Rendezvous with detection differs from the usual rendezvous problem in that two mobile agents not only accomplish rendezvous whenever this is possible, but can also detect the impossibility of rendezvous (e.g., due to symmetrical initial positions of the agents) in which case they are able to halt. We study the problem of rendezvous with and without detection of two anonymous mobile agents in a synchronous ring. The agents have constant memory and each of them possess one or more tokens which may be left at some nodes of the ring and noticed later. We derive sharp bounds for the case of at most two tokens per agent and also explore trade-offs between the number of tokens available to the agents and the time needed to accomplish rendezvous with detection.

materiál: Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis, Danny Krizanc : The Power of Tokens: Rendezvous and Symmetry Detection for two Mobile Agents in a Ring, SOFSEM, 2008


23.5.2008 o 11:00     Rasťo Královič (FMFI UK ) : Voľba šéfa v modeli s chybnými linkami

Abstrakt:  Študujeme synchrónny model, v ktorom sa v každom kroku môžu strácať správy: ak sa v celej sieti v danom kroku posiela m správ, kde m=c(G) je garantované, že aspoň jedna správa sa doručí. V prednáške spomenieme nové výsledky týkajúce sa voľby šéfa na kruhoch a úplných grafoch v tomto modeli.


16.5.2008 o 11:00     Martin Stanek (FMFI UK ) : Hľadanie rýchlych hašovacích funkcií

Abstrakt:  Kryptografické hašovacie funkcie sú dôležité objekty v mnohých kryptografických konštrukciách. Ich rýchlosť (efektívnosť výpočtu funkčnej hodnoty) je preto dôležitým parametrom, ktorý chceme zlepšovať.

V prednáške sa budeme venovať hľadaniu rýchlych hašovacích funkcií(HF), pričom

1. ukážeme model, v ktorom sa hodnotí bezpečnosť HF založených na blokových šifrách,

2. odvodíme horné limity pre rýchlosť bezpečných HF,

3. ukážeme, že prirodzené zovšeobecnenia klasických konštrukcií HF dosahujúce tieto limity už bezpečné nie sú.


7.5.2008 o 13:15     Martin Pal (Google ) : General Auction Mechanism for Search Advertising

Abstrakt:  Internet search advertising is often sold by an online automated auction. Typically a fixed number of slots $k$ is available, and have to be allocated among $n$ advertisers each of whom desires to display an ad. Several mechanisms to price the slots and allocate them to advertisers are in use, including variants of the Generalized Second Price (GSP) mechanism, as well as mechanisms from the Vickrey-Clarke-Groves (VCG) family that are designed to be truthful for profit maximizing bidders. Extensions to account for things like position constraints and reserve prices have also been studied.

It turns out that many of these auction mechanisms can be viewed as computing a "bidder-optimal stable matching" with suitably defined preferences of the auction participants. This allows us to apply the theory of stable matchings pioneered by Gale and Shapley to search auctions. We define a general stable matching model with money in which many of the existing auctions can be expressed, and propose novel mechanisms for diverse sets of bidders that fit within our model. We show that in this model, a bidder-optimal stable matching always exists (under a mild non-degeneracy assumption), and that a mechanism based on computing such matching is truthful. Most importantly, we give an algorithm to compute a bidder-optimal matching in polynomial time.

materiál: Gagan Aggarwal, S. Muthukrishnan, David Pal, Martin Pal: General Auction Mechanism for Search Advertising, ,


25.4.2008 o 11:00     David Pal ( ) : Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning

Abstrakt:  We study the potential benefits of unlabeled data to classification prediction to the learner. For that purpose we introduce a simplistic model of semi-supervised learning (SSL). We compare learning in the SSL model to the standard, supervised PAC (distribution free) model, considering both the realizable and the unrealizable (agnostic) settings.

Roughly speaking, our conclusion is that access to unlabeled samples cannot provide sample size guarantees that are better than those obtainable without access to unlabeled data, unless one postulates very strong assumptions about the distribution of labels.

In particular, we prove that for basic hypothesis classes over the real line, if the distribution of unlabeled data is `smooth', knowledge of that distribution cannot improve the labeled sample complexity by more than a constant factor (e.g., 2). We conjecture that a similar phenomena holds for any hypothesis class and any unlabeled data distribution. We also discuss the utility of semi-supervised learning under the common "cluster assumption" concerning the distribution of labels, and show that even in the most accommodating cases, where data is generated by two uni-modal label-homogeneous distributions, common SSL paradigms may be misleading and inflict poor prediction performance.

materiál: Shai-Ben David, Tyler Lu , David Pal: Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning, COLT, 2008

2007



7.12.2007 o 11:00     Rasťo Královič (FMFI UK ) : Koľko treba vedieť o budúcnosti?

Abstrakt:  Ako "online" sa zvyknú označovať problémy, ktoré požadujú čiastkový výstup bez úplnej znalosti vstupu: typický príklad je server, ktorý musí spracovať každú prichádzajúcu požiadavku skôr, ako príde nasledujúca. Najrozšírenejšou mierou zložitosti je tzv. "competitive ratio", ktoré porovnáva dosiahnuté riešenie s optimálnym, čím kvantifikuje stratu kvality spôsobenú nedostatkom informácie o vstupe. V článku zavádzame alternatívnu mieru, ktorá charakterizuje online problémy podľa najmenšieho množstva dodatočnej informácie, potrebnej na získanie optimálneho riešenia. Novú mieru demonštrujeme na analýze dvoch typických online problémov.

materiál: S. Dobrev, R. Královič, D. Pardubská: How Much Information About the Future is Needed?, SOFSEM 2008,


30.11.2007 o 11:00     Janka Katreniakova (FMFI UK ) : Visual Exploration of RDF Data

Abstrakt:  We have developed and implemented infrastructure and RDF storage for the Semantic Web. When we filled it with data the need for some tool that could explore the data became evident. Unfortunately, none of existing solutions fulfills requirements imposed by the data and users expectations. This paper presents our RDF visualizer that was designed specifically to handle large RDF data by means of incremental navigation. A detailed description of the algorithm is given as well as actual results produced by the visualizer.


23.11.2007 o 11:00     Stanislav Miklik (FMFI UK ) : Picking up the Pieces: Self-Healing in Reconfigurable Networks

Abstrakt:  We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. We present a new algorithm, DASH, that provably ensures that: 1) the network stays connected even if an adversary deletes up to all nodes in the network; and 2) no node ever increases its degree by more than 2 log n + 1, where n is the number of nodes initially in the network. DASH is fully distributed; adds new edges only among neighbors of deleted nodes; and has average latency and bandwidth costs that are at most logarithmic in n. DASH has these properties irrespective of the topology of the initial network, and is thus orthogonal and complementary to traditional topology-based approaches to defending against attack. We also prove lower-bounds showing that DASH is asymptotically optimal in terms of minimizing maximum degree increase over multiple attacks. Finally, we present empirical results on power-law graphs that show that DASH performs well in practice, and that it significantly outperforms naive algorithms in reducing maximum degree increase.

materiál: Jared Saia and Amitabh Trehan: Picking up the Pieces: Self-Healing in Reconfigurable Networks, ,


16.11.2007 o 11:00     Stefan Dobrev (SAV ) : Local Edge Colouring of Yao-like Subgraphs of Unit Disk Graphs

Abstrakt:  The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like subgraphs of Unit Disc Graphs. These are geometric graphs such that for some positive integers l,k the following property holds at each node v: if we partition the unit circle centered at v into 2k equally sized wedges then each wedge can contain at most l points different from v. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k and l, but not on the size of the graph) number of hops away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl+1 and this is optimal for local algorithms (since the maximal degree is 2kl and a colouring with 2kl colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.

materiál: J. Czyzowicz, S. Dobrev, E. Kranakis, J. Opatrny and J. Urrutia: Local Edge Colouring of Yao-Like Subgraphs of Unit Disk Graphs, SIROCCO'07, pp. 195-207, Springer 2007


26.10.2007 o 11:00     Tomáš Plachetka (FMFI UK ) : Rozvrhovanie nezavislych uloh na paralelne procesory

Abstrakt:  Rozvrhovanie nezavislych uloh na paralelne procesory je NP-tazky problem. Online verzia tohto problemu nepredpoklada kompletnu znalost casov jednotlivych uloh. Existujuce pristupy vacsinou uvazuju pravdepodobnostny model, ktory predpoklada, ze tieto casy su generovane podla normalneho rozlozenia s a-priori znamymi parametrami. V tom pripade je cielom minimalizovat ocakavany paralelny cas. My sa zaoberame deterministickym modelom, ktory predpoklada a-priori znalost maximalneho a minimalneho casu spomedzi vsetkych uloh. Cielom v tomto modeli je minimalizovat absolutny paralelny cas cez vsetky permutacie uloh. Na seminari predvedieme vysledky analyzy niekolkych algoritmov. Hlavnym novym vysledkom je, ze online rozvrhovacie algoritmy s ciastocnou a-priori znalostou casov rozvrhovanych uloh sa daju nahradit podobne efektivnym deterministickym online algoritmom, ktory tuto znalost nevyzaduje.


12.10.2007 o 11:00     Rasťo Královič (FMFI UK ) : Rapid Almost-Complete Broadcasting in Faulty Networks

Abstrakt:  This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number T , or a fraction ?, of sent messages can be lost depending on which quantity is larger.

As the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time O(D log n) where D is the diameter of the network and n is the number of vertices.

Moreover, for complete graphs under some additional conditions (sense of direction, or ? < 0.55) the remaining constant number of vertices can be informed in the same time, i.e. O(log n).


21.9.2007 o 11:00     Stefan Dobrev (SAV ) : Local Computation in Location-Aware Ad-Hoc Networks

Abstrakt:  In the same way as the spread of computer networks has motivated the study of distributed algorithms, the increase in size of these networks and appearance of wireless networks has caused significant research interest in local algorithms, in which the decision at each node is computed based only on the information contained in the node's local neighbourhood (i.e., up to k hops away, for some constant k). Local algorithms are of particular interest in wireless ad-hoc networks (e.g., sensor networks), where the dynamic and transient nature of the network requires fast adaptability and severely limits applicability of centralized and global approaches.

However, there are strong limitations on what can be computed locally, typically caused by the underlying global nature of the problem (e.g., constructing a spanning tree) or by the possibility of local symmetry. One way to deal with the problem is a relaxation of the requirements on the solution (e.g., instead of finding a spanning tree, find a sufficiently sparse subgraph), another is to consider additional structural information available in the network to break the symmetry.

In this talk, we examine how geographic information (i.e., the nodes know their GPS coordinates-are location-aware) can be exploited in ad-hoc networks modeled by unit-disc graphs. We consider the problems of locally constructing suitable (planar, connected, with good spanner properties, of low cost) subgraphs of the underlying unit-disc graph, as well as various graph covering and colouring problems.


14.9.2007 o 11:00     Viliam Geffert (UPJŠ Košice ) : Minimizing Minimized Deterministic Finite State Automata

Abstrakt:  We shall present a method for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimal DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyperminimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction works also for finite state transducers producing outputs.

Within a class of finitely differing languages, the hyper-minimized automaton is not necessarily unique. There may exist several non-isomorphic machines using the minimum number of states, each accepting a different finite variation of the original language. However, we show that there are large structural similarities among these smallest automata.


4.5.2007 o 11:00     Ján Šturc (FMFI UK ) : Efficient String Matching and Easy Bottom-Up Parsing

Abstrakt:  Porovnam tri algoritmy na on-line vyhľadávanie podreťazcov zaloložené na tej istej myšlienke: Dömölkiho algoritmus (1964), Aho Corasickovej algoritmus (1975) a tabuľkový algoritmus, ktorý môžeme považovať za šikovnú implementáciu oboch na RAMe s jednotkovou cenou inštrukcie. Ukážem ako sa takýto automat dá využiť na ľahkú implementáciu syntaktickej analýzy zdola nahor. Realizujeme SLR(1) analyzu, ktorô zovšeobecníme na analýzu pomocou spätne deterministických kontext senzitívnych pravidiel a spätne deterministické preisovanie. Na záver poviem o diagnostike a zotavení z chýb v takomto kompilátore.


20.4.2007 o 11:00     Ľuboš Steskal (FMFI UK ) : Infinite Computations and a Hierarchy in Delta_3

Abstrakt:  We shall introduce a computational model capable of infinite computation. This model gives rise to a hierarchy of families between the $\Sigma_2$ and $\Delta_3$ levels of the arithmetic hierarchy. The structure of the top five levels of this hierarchy is in some sense similar to the structure of the Chomsky hierarchy, while the bottom levels are reminiscent of the bounded oracle query hierarchy.


13.4.2007 o 11:00     Martin Nehéz ( ) : An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques

Abstrakt:  Motivated by compact routing in large-scale and almost all networks, we will study interval routing schemes in Erdös-Rényi random graphs. C. Gavoille and D. Peleg (2001) posed a conjecture of whether almost all networks support a shortest-path interval routing scheme with 1 interval. We answer this question partially by proving that in almost all networks, there is an interval routing scheme with 1 interval up to additive stretch 2. Our proof is based on the phase transition property in the theory of dominating cliques in random graphs.


27.3.2007 o 11:00     Věra Kurková (UI AV ČR) : Estimates of data complexity in neural-network learning

Abstrakt:  Data complexity with respect to a particular class of neural networks can be measured by the magnitude of a certain norm of either the regression function induced by a probability measure describing the data or a function interpolating a sample of data. The norm is tailored to a type of computational units in the network class. It is shown that for data for which this norm is ``small'', convergence of infima of error functionals over networks with increasing number of hidden units to the global minima is relatively fast. Thus for such data, networks with a reasonable model complexity can achieve good performance during learning. For perceptron networks, the relationship between data complexity, data dimensionality and smoothness will be described.


22.3.2007 o 14:00     Jose L Marzo (University of Girona) : Traffic grooming in Optical Networks

Abstrakt:  Recent achievements in optical transmission and switching lead computer networks to design new control and management mechanisms in order to cope near future huge amount of traffic in Internet. This talk is organized in three parts. In first one, traffic merging main principles are described, this includes classical and statistical multiplexing techniques and the role of label switching technologies as a way of traffic aggregation in electronic networks. The MPLS case is presented as example and also as capable of tunneling. In the second part, optical transmission, (D)WDM and the basis of optical switching technologies are presented as crucial factor in optical development, this part also includes the buffer less drawback of this systems and traffic grooming principles in WDM networks. Finally, a brief overview about our G+ arquitechture proposal for traffic grooming in which we are working on. In this proposal traffic grooming is carried out minimizing the number opto-electronic transponders.


13.3.2007 o 8:50     Viliam Geffert (UPJŠ Košice) : Complementing Two-Way Finite Automata

Abstrakt:  We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts.

For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n8)-state 2nfa. Here we also make 2nfa's halting. This allows the simulation of unary 2nfa's by probabilistic Las Vegas two-way automata with O(n8) states.


9.3.2007 o 11:00     Jana Katreniaková (FMFI UK) : Mental map preserving cluster expansion

Abstrakt:  For representing large amounts of information the traditional graph models are not sufficient. Graph models with hierarchical structure were introduced, compound graphs being the most general ones. Navigation in large graphs utilizes the operations expand and contract cluster to get refined or coarsened view. In this article we introduce an algorithm for cluster expansion. Since the algorithm is based on local changes of the cluster and its neighbors, it preserves user's mental map.


2.3.2007 o 11:00     Jiří Wiedermann (UI AV ČR) : Amorfni pocitace a jejich vypocetni sila

Abstrakt:  Amorfni pocitace se lisi od klasickych prakticky po vsech strankach. Jejich architektura je nahodna, protoze jsou tvoreny mnozstvim identickych vypocetnich jednotek nahodne rozsetych v rovine. Vypocetni sila techto jednotek je omezena, protoze se jedna o pravdepodobnostni automaty..Komunikacni moznosti automatu jsou take omezene: jednotky si mohou vymenovat zpravy radiem pouze v malem dosahu. Situaci komplikuje i skutecnost, ze v systemu neexistuje globalni cas - jednotky pracuji asynchonne. Navic, jednotky nemaji moznost zjisit vysilaci kolize - to znamena, ze zprava je prijata pouze neni-li soucasne rusena jinym vysilanim; prijimac ale nedovede rozlisit pripad ruseni od nevysilani. Muze vysledny system provadet turingovske vypocty? Jake musi byt vlastnosti prilusneho komunikacniho grafu, aby system efektivne fungoval? Jak musi vypadat komunikacni protokol na urovni uzlu takoveho grafu? Odpovidajici vypocetni teorie vyuziva vlastnosti nahodnych grafu a pravdepodobnostni algoritmy.


23.2.2007 o 11:00     Jana Dvořáková (FMFI UK) : A Transducer-Based Framework for Streaming XML Transformations

Abstrakt:  The streaming processing of XML transformations is practically needed especially if we have large XML documents or XML data streams as the input for a transformation. We introduce a formal framework for XML transformations, which enables us to analyze the complexity of streaming processing. The framework includes both a model for general (tree-based) transformations and a model for streaming transformations. The models are based on tree transducers. We demonstrate the usage of the framework by identifying a subclass of general transformations which can be realized by the streaming model in one pass using a stack to hold temporary data.

2006



10.11.2006 o 11:00     Dana Pardubská (FMFI UK) : WPTM - alternatívna charakterizácia alternovania

Abstrakt:  WPTM ( Wireless Parallel Turing machine) je výpočtový model, ktorého návrh bol inąpirovaný základnými vlastnos»ami bezdrôtových mobilných komunikačných sietí. V podstate ide o deterministický Turingov stroj obohatený o moľnos» vytvárania nových komunikujúcich procesov, v ktorom bezdrôtová komunikácia medzi procesmi prebieha prostredníctvom explicitne určených kanálov. Zameriame sa na vz»ah WPTM a ATM. Ukážeme vzájomné simulácie, ktoré zachovávajú čas aj priestor. Tým získame nielen alternatívnu charakterizáciu alternovania, ale ako dôsledok aj charakterizáciu tried NCi a NC.


27.10.2006 o 11:00     Richard Ostertág (FMFI UK) : Analýza selektorov pre selektívne šifrovanie

Abstrakt:  Niektoré aplikácie požadujú vysokú rýchlosť šifrovania aj za cenu zníženia jeho bezpečnosti. Zvýšenie rýchlosti sa dá pri zachovaní pôvodného (kvalitného ale výpočtovo náročného) šifrovacieho algoritmu dosiahnuť napríklad zašifrovaním len časti dát. Článok analyzuje bezpečnosť algoritmov selektívneho šifrovania postavených na rôznych metódach výberu tejto časti.


13.10.2006 o 11:00     Branislav Katreniak (FMFI UK) : On the Inability of Gathering by Asynchronous Mobile Robots with Initial Movements

Abstrakt:  Consider a community of simple autonomous robots freely moving in the plane. The robots are decentralized, asynchronous, deterministic without the common coordination system, identities, direct communication, memory of the past, but with the ability to sense the positions of the other robots. Existing results show the inability of gathering in this model and solve the gathering problem in the model extended by the multiplicity detection capability. However, the previous results rely on the fact that the robots are intially not moving. We prove that the gathering problem is unsolvable in the model with initial movement vectors even with the multiplicity detection capability.


2.6.2006 o 11:00     Tomáš Záthurecký (FMFI UK) : Nepravidelné bunkové asynchrónne automaty

Abstrakt:  Definujeme nový výpočtový model nepravidelných asynchrónnych bunkových automatov a skúmame ich výpočtovú silu. Nepravidelný asynchrónny bunkový automat je graf, ktorý má v každom vrchole konečne stavový automat, ktorý vidí svoj stav a stavy svojich susedov. Všetky vrcholy sú riadené rovnakým programom, ktorý nazveme prechodová schéma. V každom kroku výpočtu urobia prechod niektoré vrcholy. Požaduje sa, aby výsledok výpočtu celého automatu (za predpokladu, že ten automat je dostatočne veľký) bol nezávislý od výberu počítajúcich vrcholov (za predpokladu, že ten výber je spravodlivý) a ich grafu prepojení (za predpokladu, že ten graf je súvislý). Dokážeme, že nepravidelné asynchrónne bunkové automaty majú rovnakú výpočtovú silu ako Turingove stroje.


26.5.2006 o 11:00     Michal Forišek (FMFI UK) : Výskum súťaží v programovaní

Abstrakt:  V poslednych rokoch sa v komunite okolo sutazi v programovani rozmaha trend vedeckeho pristupu k tejto oblasti. Ukazuje sa, ze sa v tejto oblasti daju uplatnit poznatky nielen z teoretickej informatiky (testovanie rieseni, tvorba sutaznych uloh), ale aj statistiky (zistovanie vhodnosti pouzivanych foriem hodnotenia), pedagogiky a psychologie.

Koncom januara 2006 sa v nemeckom Dagstuhle uskutocnil prvy workshop Perspectives on Computer Science Competitions for (High School) Students (http://www.bwinf.de/competition-workshop/). Publikacie zaslane na tento workshop sa snazia vymedzit temy vyskumu v tejto oblasti. Na seminari strucne zhrniem vysledky workshopu, podrobnejsie sa budem zaoberat hlavne temou, na ktorej pracujem aj ja: automaticke testovanie sutaznych rieseni.


5.5.2006 o 11:00     Vladimír Koutný (FMFI UK, Paderborn University) : Large-Scale Sensor Network Experiment

Abstrakt:  We extend previous work on 1QK routing protocol by performing several experiments with real hardware (50 motes) in various real-world scenarios, including a supermarket as an originally planned deployment. Based on the results we focus on several aspects of the protocol in order to improve its performance and reliability. Scalability aspects are also of a great importance since the full potential of such a network arise with thousands of sensors.


21.4.2006 o 11:00     Dávid Pál (University of Waterloo) : A Sober look at Clustering Stability

Abstrakt:  Stability is a common tool to verify the validity of sample based algorithms. In clustering it is widely used to tune the parameters of the algorithm, such as the number k of clusters. In spite of the popularity of stability in practical applications, there has been very little theoretical analysis of this notion. In this paper we provide a formal definition of stability and analyze some of its basic properties. Quite surprisingly, the conclusion of our analysis is that for large sample size, stability is fully determined by the behavior of the objective function which the clustering algorithm is aiming to minimize. If the objective function has a unique global minimizer, the algorithm is stable, otherwise it is unstable. In particular we conclude that stability is not a well-suited tool to determine the number of clusters - it is determined by the symmetries of the data which may be unrelated to clustering parameters. We prove our results for center-based clusterings and for spectral clustering, and support our conclusions by many examples in which the behavior of stability is counter-intuitive.


7.4.2006 o 11:00     Rasťo Královič (FMFI UK) : Broadcasting v prostredí s chybnými linkami

Abstrakt:  Problem sirenia informacie (broadcasting) je zakladnym komunikacnym problemom v distribuovanych sietach. V prednaske sa zameriame na synchronne point-to-point siete a zakladnou otazkou je cas potrebny na broadcasting v najhorsom pripade v tzv. all-port modeli, v ktorom kazdy vrchol moze v jednom kroku informovat vsetkych svojich susedov. V pripade spolahlivej siete je tento cas rovny priemeru grafu. Prezentujeme niekolko deterministickych modelov chyb liniek (staticke chyby, dynamicke chyby, proporcionalne modely) a ukazeme vysledky pre rozne triedy grafov.


31.3.2006 o 11:00     Richard Královič (FMFI UK) : Jarná škola ADONET/COST293 - prehľad prednášok

Abstrakt:  20.-24. marca 2006 sa v Budapešti konala jarná škola "ADONET/COST293 Spring School on Combinatorial Optimization and Communication Networks". Na seminári zaznie stručný prehľad tém, ktoré boli odprednášané. Prednášky boli venované grafovo-teoretickým problémom, praktickým stránkam komunikačných sietí a praktickému riešeniu ťažkých problémov (napr. pri návrhu VLSI obvodov). Informácie o jarnej škole sú dostupné na adrese http://www.cs.elte.hu/~acss2006/.


3.3.2006 o 11:00     Jiří Wiedermann (AV ČR Praha) : Vypocetni modely kognitivnich systemu

Abstrakt:  Kognitivni vypocetni systemy jsou vypocetne rizene evolucni systemy, urcene k provozovani podobnych aktivit, pomoci kterych zive organizmy nachazeji, vnimaji, ziskavaji, zpracovavaji, uchovavaji a vyuzivaji informace potrebne k udrzeni sveho zivota a jeho rozvoji. Modelovanim techto systemu a analyzou prislusnych modelu budeme hledat odpovedi napr. na nasledujici otazky:

  • jsou kognitivni systemy spise konecne automaty anebo Turingovy stroje?
  • mohou tyto systemy prekonat Turingovy stroje?
  • jaka je vlastne vypocetni sila techto systemu?
  • jak funguje evoluce a jeji ridici mechanizmy?
  • existuje evoluce produkujici neohraniceny narust vypocetni slozitosti kognitivnich systemu?
  • jake jsou algoritmicke principy kognice?
  • co je specificke pro humanoidni mysl?
  • jake jsou predstavy o mechanizmech vzniku a fungovani vedomi?
  • lze definovat inteligenci pomoci nejakeho vypocetniho kognitivniho modelu?



4.1.2006 o 13:00     Daniel Štefankovič (FMFI UK, University of Rochester) : Crossing numbers of graphs.

Abstrakt:  The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. Chojnacki (1934) and Tutte (1970) showed that if the odd crossing number of a graph is zero then its crossing number is zero. We will show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems). Joint work with Michael Pelsmajer and Marcus Schaefer.

2005



16.12.2005 o 11:00     Miroslav Dudík (Princeton University) : Princip najvacsej entropie a modely rozsirenia biologickych druhov

Abstrakt:  Modelovanie rozsirenia druhov je dolezitou ulohou v biologii prirodnych rezervacii a ekologii. Cielom je na zaklade popisu prirodnych podmienok v danom regione a lokalit, kde bol urcity druh zivocicha alebo rastliny pozorovany, odhadnut, ake podmienky tento druh vyhladava. Z pohladu statistickych metod a pocitacoveho ucenia tato uloha prinasa dve tazkosti: maly pocet lokalit vyskytu a chybajuce informacie o tom, kde sa druh nenachadza (priklady absencie/zaporne priklady). Nasim navrhom je pouzit princip najvacsej entropie (maxent), ktory umoznuje statisticky podlozeny pristup na preklenutie tychto tazkosti.

V nasom prispevku popiseme maxent a vysvetlime, ako suvisi s metodou najvacsej vierohodnosti. Navrhneme oslabenu verziu maxent-u, vdaka ktorej ziskame neasymptoticke odhady presnosti ziskanych modelov. Tieto odhady klesaju rychlo s rastucou velkostou vyberu a rastu len logaritmicky s poctom premennych popisujucich prirodne podmienky. V druhej casti navrhneme novu metodu vypoctu modelov maxent-u zalozenu na suradnicovom spade a dokazeme jej konvergenciu. Tento typ optimalizacie je zvlast vhodny pri velkom (dokonca nekonecnom) pocte premennych. V zavere ukazeme, ako mozno pouzit maxent v problemoch s nerovnomernym vyberom.

Spoluautori: Rob Schapire (Princeton University), Steven Phillips (AT&T Labs Research).


30.9.2005 o 11:00     Dana Pardubská (FMFI UK) : Alternatívna charakterizácia synchronizovaného alternovania

Abstrakt:  V prednáąke navrhneme nový výpoc(tový model, ktorého návrh je inąpirovaný základnými vlastnost(ami bezdrôtových mobilných komunikac(ných sietí. V podstate ide o deterministický Turingov stroj obohatený o moľnost( vytvárania nových komunikujúcich procesov, pric(om bezdrôtová komunikácia medzi procesmi prebieha prostredníctvom explicitne urc(ených kanálov. Dokáľeme, ľe výpoc(tovo sú tieto stroje c(asovo aj priestorovo ekvivalentné synchronizovaným alternujúcim Turingovým strojom. To ukazuje, ľe synchronizované alternovanie moľno nahradit( deterministickým paralelizmom s moľnost(ou neobmedzenej komunikácie a naopak.


9.9.2005 o 11:00     Martin Pál (Cornell University) : Sampling Bounds for Stochastic Optimization

Abstrakt:  A large class of stochastic optimization problems can be modeled as minimizing an objective function f that depends on a choice of a vector x in X, as well as on a random external parameter omega in Omega given by a probability distribution p. The value of the objective function is a random variable and often the goal is to find an x in X to minimize the expected cost E_omega[f_omega(x)]. Each omega is referred to as a scenario. We consider the case when Omega is large or infinite and we are allowed to sample from p in a black-box fashion. A common method, known as the SAA method (sample average approximation), is to pick sufficiently many independent samples from p and use them to approximate p and correspondingly E_omega[f_omega(x)]. This is one of several scenario reduction methods used in practice.

There has been substantial recent interest in two-stage stochastic versions of combinatorial optimization problems which can be modeled by the framework described above. In particular, we are interested in the model where a parameter lambda bounds the relative factor by which costs increase if decisions are delayed to the second stage. Although the SAA method has been widely analyzed, the known bounds on the number of samples required for a (1+e) approximation depend on the variance of p even when lambda is assumed to be a fixed constant. Shmoys and Swamy proved that a polynomial number of samples suffice when f can be modeled as a linear or convex program. They used modifications to the ellipsoid method to prove this.

In this talk we give a different proof, based on earlier methods of Kleywegt, Shapiro, Homem-De-Mello and others, that a polynomial number of samples suffice for the SAA method. Our proof is not based on computational properties of f and hence also applies to integer programs. We further show that small variations of the SAA method suffice to obtain a bound on the sample size even when we have only an approximation algorithm to solve the sampled problem. We are thus able to extend a number of algorithms designed for the case when p is given explicitly to the case when p is given as a black-box sampling oracle.


27.5.2005 o 11:00     Masami Ito (Kyoto Sangyo University) : Nondeterministic directable automata and languages

Abstrakt:  Let A=(S,X,M) be an automaton. Then A is called a directable automaton if there exists a word u over X such that M(s,u)=M(t,u) holds for any two states s and t. Moreover, u is called a directing word of A. It can be shown that the set of all directing words of a directable automaton is regular. Assume that A=(S,X,M) is a directable automaton. Let d(A)=min{|u|: u is a directing word of A}. For any positive integer n, d(n) denotes the value max{d(A): A=(S,X,M) is a directable automaton and |S|=2}. J. Cerny conjectured d(n)=(n-1)2. However, this conjecture is still open. In the talk, we generalize the notion(s) of directability to the class of nondeterministic automata. Moreover, we consider related classes of languages and the nondeterministic version of Cerny's conjecture.


20.5.2005 o 11:00     Michal Forišek (FMFI UK) : Optimal Perfect Token Distribution on Trees

Abstrakt:  In a distributed environment consisting of processors and communication channels between them one of the most important problems is {\em load balancing} -- redistributing jobs between the processors in such a way that each processor ends with roughly the same amount of work. In this area {\em token distribution} represents an important variant, where all jobs are assumed to be indivisible and of unit size.

We consider the problem of token distribution on networks having the topology of an undirected tree. We solve two open problems. Our first algorithm computes a perfect token distribution using symptotically optimal memory per node. Our second algorithm is the first distributed polynomial-time algorithm to compute a perfect token distribution in an optimal number of token moves.


6.5.2005 o 11:00     Branislav Katreniak (FMFI UK) : Biangular Circle Formation by Asynchronous Mobile Robots

Abstrakt:  Consider a community of simple autonomous robots freely moving in the plane. The robots are decentralized, asynchronous, deterministic without the common coordination system, identities, direct communication, memory of the past, but with the ability to sense the positions of the other robots. We study the problem of forming an absolutely symmetric formation - regular circle. Unlike the existing algorithms for similar problems that have supposed a stronger model and guaranteed only convergence to a final formation, we are interested in solving the problem for fully asynchronous model. Unfortunately, the problem in general is very hard under these circumstances and seems to be unsolvable. We present an algorithm that solves an intermediate problem, the biangular circle formation, deterministically in finite time.


29.4.2005 o 11:00     Richard Královič (FMFI UK) : On Semi-perfect 1-factorizations

Abstrakt:  The perfect 1-factorization conjecture by A. Kotzig asserts the existence of a 1-factorization of a complete graph K_2n in which any two 1-factors induce a Hamiltonian cycle. This conjecture is one of the prominent open problems in graph theory.

Apart from its theoretical significance it has a number of applications, particularly in designing topologies for wireless communication.

Recently, a weaker version of this conjecture has been proposed for the case of semi-perfect 1-factorizations. A semi-perfect 1-factorization is a decomposition of a graph G into distinct 1-factors F_1,...,F_k such that F_1 U F_i forms a Hamiltonian cycle for any 1<i≤k.

We show that complete graphs K_2n, hypercubes Q_2n+1 and tori T_2n x 2n admit a semi-perfect 1-factorization.