# Poprzednie referaty

16.03.2017 14:15 Jakub Cisło, Grzegorz Jurdziński |
Tight Hardness Results for LCS and other Sequence Similarity Measures |

09.03.2017 14:00 Sylwester Klocek, Wojciech Kruk |
The Alternating Stock Size Problem and the Gasoline Puzzle |

05.01.2017 14:15 Jan Derbisz, Jakub Łabaj |
How to sort by walking on a tree |

We consider a tree with n vertices. On vertex number |

15.12.2016 14:15 Michał Glapa, Franciszek Stokowacki |
Maximum matching with algebraic methods |

In 2006, a celebrated result by Mucha and Sankowski stated that the maximum matching problem can be done by Gaussian elimination. The complexity of this algorithm depends on matrix multiplication, but certainly beats O(n |

08.12.2016 Lech Duraj |
A short tale of matrix multiplication |

In recent years, some new algorithms for matrix multiplication problem were presented. Each of them is, however, only slightly faster than previous ones, while requiring substantially more complex analysis. Because of this, the long-standing question of optimal matrix multiplication algorithm seems even harder. In my presentation, a short survery of the matrix multiplication algorithm is given. The presentation is based on François Le Gall's survey lecture of 2014. |

01.12.2016 Aleksandra Mędrek, Krzysztof Maziarz |
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back |

The paper by Aleksander Mądry describes a new approach to the maximum flow problem. We define an electrical flow by assigning resistances to every edge and minimizing total energy instead of maximizing flow. Any flow network can be reduced to some electrical flow problem, using auxiliary reductions to some bipartite matching problems. The main result is a new maximum flow algorithm, working in O(m10/7). The presentation will cover a simpler, O(m3/2) version of the algorithm. |

24.11.2016 Dominika Salawa, Jakub Cisło |
Greedy algorithms for Steiner forest |

The paper, resolves a long-standing open question: is the greedy approach for Steiner forest problem optimal up to multiplicative constant? The result by Anupam Gupta and Amit Kumar proves that in fact it is, with constant being at most 96. While some approximation algorithms for this problem, using linear programming, were previously known, this is the first known bound for a greedy algorithm. |

17.11.2016 Patryk Gołębiowski, Wojciech Kruk |
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms |

In the last decade, there has been a substantial amount of research in finding routing algorithms designed specifically to run on real-world graphs. The paper by Colin White analyzes some of these algorithms and gives lower bounds for their complexity. |

10.11.2016 Magdalena Gargas, Mateusz Jachna |
Max flows in O(nm) time, or better |

A new max-flow algorithm with O(nm + m16/15 log2 n) time complexity is presented. By combining this with previous results, an O(nm) algorithm may be obtained, resolving a long-standing open question. This work is due to James B. Orlin. |

03.11.2016 Krzysztof Francuz, Szymon Łukasz |
Fast and simple connectivity in graph timelines |

The presented paper (by J. Łącki and A. Karczmarz) deals with graph timelines - graphs with edges being created and destroyed over time. There is an effective algorithm for answering queries about reachability (finding a path between two given vertices) and biconnectivity (two disjoint paths) over some given time intervals. |

27.10.2016 Dawid Pyczek, Jakub Rówiński |
Faster deterministic sorting and priority queues in linear space |

The O(n log n) lower bound for sorting is valid only if the sorted objects allow no operations except comparing. For sorting integers, the bound can be broken - Mikkel Thorup's result of 1997 shows an O (n (log log n) |

20.10.2016 Mateusz Twaróg, Patryk Urbański |
Disjoint Set Union with randomized linking |

The most popular version of Find-Union algorithm uses path compression and linking by rank. The presented work of Goel, Khanna, Larkin and Tarjan gives an analysis of the same algorithm, but with arbitrary (randomized) linking. |

13.10.2016 G. Bukowiec, S.Klocek |
FKT algorithm |

Counting all matchings in a given graph is a #P-complete problem. However, for planar graphs it can be done in polynomial time. The FKT algorithm does it by exploiting the connection between the notions of matrix determinant and matrix permanent. |

16.03.2016 14:15 Jakub Cisło, Grzegorz Jurdziński |
Tight Hardness Results for LCS and other Sequence Similarity Measures |

- Home
- Algorithmics Research Group
- Foundations of Computer Science
- Faculty of Mathematics and Computer Science
- Contact
- Satori
- Reports on Mathematical Logic
- Forum TCS
- UsosWeb
- Informatyka na szlaku
- Photos
- People
- Maciej Bendkowski
- Szymon Borak
- Bartłomiej Bosek
- Iwona Cieślik
- Piotr Danilewski
- Lech Duraj
- Adam Gągol
- Monika Gillert
- Katarzyna Grygiel
- Jarosław Grytczuk
- Grzegorz Guśpiel
- Grzegorz Gutowski
- Grzegorz Herman
- Leszek Horwath
- Pawel M. Idziak
- Tomasz Kisielewski
- Karol Kosiński
- Marcin Kozik
- Jakub Kozik
- Tomasz Krawczyk
- Jacek Krzaczkowski
- Łukasz Lachowski
- Wojciech Lubawski
- Agnieszka Łupińska
- Grzegorz Matecki
- Piotr Micek
- Patryk Mikos
- Andrzej Pezarski
- Adam Polak
- Michał Staromiejski
- Piotr Szafruga
- Maciej Ślusarek
- Bartosz Walczak
- Piotr Wójcik
- Michał Wrona
- Marek Zaionc
- Michał Zmarz

- Former colleagues