Zakład Złożoności Obliczeniowej i Analizy Algorytmów

Na najbliższym (18 II) seminarium zakładowym wystąpi Nadieżda Dolmatowa (Instytut Matematyczny) i opowie o pracy:

Atsushi Kaneko, Katsuhiro Ota "On minimally (n,l)- Connected Graphs", Journal of Combinatorial Theory, series B 80, 156-171 (2000).

Serdecznie zapraszamy.

Dnia 5.2.2010 (piątek) o godzinie 10:15 w sali 119 Instytutu Informatyki UWr odbędzie się seminarium na którym wystąpi Dariusz Kowalski (University of Liverpool).

Tematem seminarium będzie
Deterministyczna komunikacja na kanale radiowym.

Streszczenie:

Tematem wykładu jest efektywna komunikacja na kanale radiowym za pomocą deterministycznych protokołów. Kanał radiowy składa się z niezależnych stacji komunikujących się poprzez transmitowanie pakietów przez dzielone medium
komunikacyjne. Transmitowany pakiet jest dostarczany do celu (lub wielu docelowych stacji) jedynie jeśli w czasie jego transmisji żaden inny pakiet nie był transmitowany. Pakiety pojawiają sie w stacjach, gdzie są następnie

Na najbliższym seminarium ZZOiAA wystąpi ponownie absolwent naszego instytutu Aleksander Mądry.

Temat wystąpienia:
Faster generation of random spanning trees

Streszczenie:
We set forth a new algorithm for generating approximately uniformly random spanning trees in undirected graphs. We show how to sample from a distribution that is within a multiplicative (1 + delta) of uniform in expected time O*(m\sqrt{n} log 1/delta). This improves the sparse graph case of the best previously known worst-case bound of O(min(mn,n^{2.376})), which has stood for twenty years.

To achieve this goal, we exploit the connection between random walks on graphs and electrical networks, and we use this to introduce a new approach to the problem that integrates discrete random walk-based techniques with continuous linear algebraic methods. We believe that our use of electrical networks and sparse linear system solvers in conjunction with random walks and combinatorial partitioning techniques is a useful paradigm that will find further applications in algorithmic graph theory.

Na najbliższym seminarium wystąpi Aleksander Mądry i przedstawi swoje najnowsze wyniki dotyczące aproksymacji problemu komiwojażera. Jego praca została uznana za najlepszą pracę na SODA'10.

Wystąpienie będzie prowadzone po angielsku.

Streszczenie:

Approximating the Asymmetric Traveling Salesman Problem

The traveling salesman problem (TSP) - the problem of finding the shortest tour through a set of cities - is the prototypical combinatorial optimization problem. It comes in two flavors, the symmetric (STSP) and asymmetric (ATSP) versions; the latter corresponds to the setting in which the cost of traveling from A to B might differ from the cost from B to A. Whether one can efficiently find solutions in the asymmetric case that are within a constant factor of optimal has proved to be elusive despite considerable efforts, while the same question in the symmetric case has been settled for decades.

Na najbliższym seminarium gościnnie wystąpi Klara Zielińska.

Streszczenie wystąpienia:

Presentation of string-like structures containing sets. The alternative for a common carrier for formal languages.

In most (all?) cases we consider formal languages on flat sequences of letters. It is natural. We think about languages in a context of our natural language, which we are used to write in a shape of book-like text. However, it may be considerable to use a little more complex carrier, since we use formal languages to describe much more than that.

I shall describe some simple concept allowing more structured strings.

Na seminarium 3 XII Darek Jackowski będzie kontynuował swoje wystąpienie rozpoczęte tydzień temu.

Na najbliższym seminarium, 26 XI, wystąpi Darek Jackowski i opowie o problemach decyzyjnych dla automatów z ograniczonym niedeterminizmem.

Na najbliższym seminarium gościnnie wystąpi Alexander Okhotin (University of Turku, Finland).

Tytuł:

"Finite automata over a one-letter alphabet"

Streszczenie:

Finite automata of several kinds are known (deterministic and nondeterministic, one-way and two-way), yet all of them define the same family of languages. However, the number of states necessary to recognize one language or another significantly varies across the models. Such properties as the exponential tradeoff between one-way deterministic and nondeterministic finite automata (1DFA and 1NFA) are among the core results of automata theory. This talk is about automata over a one-letter alphabet, and the number of states necessary to convert more powerful types of automata to equivalent 1DFAs.

Na najbliższym seminarium wystąpi Marcin Skórzewski.

Opowie o pracy
Randomized minimum spanning tree algorithms using exponentially fewer random bits Seth Pettie, Vijaya Ramachandran.

Skrót: opowiem o tym, jak redukować liczbę bitów losowych w algorytmach zrandomizowanych. Motywacją jest koszt uzyskania bitów naprawdę losowych i próba derandomizacji.

Na seminarium 15 X wystąpi Tomek Cichocki i opowie o pracy

Gossiping in Social Networks Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi.

Zapraszamy!