Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium "Algorytmika"

Research seminar (FRIDAYS, usually biweekly at 14.15 in room 5060 or online)

For schedule or link to online meetings, see

If you want  to get notifications of the talks sign up to the mailing list 

Rules for PhD studens:

Google calendar:

YouTube cannel:

Lista referatów

  • 2021-04-29, godz. 12:15, online

    Jana Cslovjecsek (EPFL)

    Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

    We consider n-fold integer programming problems and their generalizations. These are integer linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent sub-problems after deleting a small number of constraints. ...

  • 2021-04-15, godz. 12:15, online

    Tomáš Masařík (Simon Fraser University)

    Flexible List Colorings in Graphs with Special Degeneracy Conditions

    For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. W...

  • 2021-04-01, godz. 12:15, online

    Michał Pilipczuk

    Reducing randomness in Isolation Lemma on decomposable graphs

    The classic Isolation Lemma of Mulmuley et al. states that if F is a non-empty family of subsets of a universe U of size n, and we draw a weight function f : U -> {1,...,2n} uniformly at random, then with probability at least 1/2 there is a unique element of F that has the minimum weight ...

  • 2021-03-18, godz. 12:15, online

    Anna Zych-Pawlewicz

    Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

    We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time O(2^{d^2}), which matches the best known parameter dependenc...

  • 2021-03-04, godz. 12:15, online (link on the seminar website)

    Łukasz Bożyk

    Vertex deletion into bipartite permutation graphs

    A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines, one on each. A bipartite permutation graph is a permutation graph which is bipartite. We study the parameterized complexity of the bipartite permutation vertex deletion problem, whic...

  • 2021-01-21, godz. 12:15, online

    Karol Węgrzycki (MPI Saarbrucken)

    Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors

    We present an O^*(2^{0.5 n}) time and O^*(2^{0.249999n}) space randomized algorithm for Subset Sum. This is the first improvement over the long-standing O^*(2^{n/2}) time and O^*(2^{n /4}) space algorithm due to Schroeppel and Shamir. This talk will also feature an introduction to the representative...

  • 2021-01-07, godz. 12:15, online

    Michał Włodarczyk (Eindhoven University of Technology)

    Parameterized Inapproximability for Steiner Orientation by Gap Amplification

    In the k\textnormal{-}\textsc{Steiner Orientation} problem, we are given a mixed graph, that is, with both directed and undirected edges, and a set of k terminal pairs. The goal is to find an orientation of the undirected edges that maximizes the number of terminal pairs for which there is a path...

  • 2020-12-17, godz. 12:15, online

    Juliusz Straszyński

    Efficient Computation of 2-Covers of a String

    Quasiperiodicity is a generalization of periodicity that has been researched for almost 30 years. The notion of cover is the classic variant of quasiperiodicity. A cover of a text T is a string whose occurrences in T cover all positions of T.   There are several algorithms computing ...

  • 2020-12-03, godz. 12:15, online

    Adam Karczmarz (UW)

    A Deterministic Parallel APSP Algorithm and its Applications

    In this talk we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has $\tilde{O}(nm+(n/d)3)$ work and $\tilde{O}(d)$ depth for any depth parameter $d\in [1,n]$. To the best of our knowledge, such a trade-off has only been previously des...

  • 2020-11-19, godz. 12:15, online (link in the calendar and sent to the mailing list)

    Céline M. F. Swennenhuis (Eindhoven University of Technology)

    A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

    In the Bin Packing problem one is given n items with different weights and m bins with a given capacity; the goal is to distribute the items over the bins without exceeding the capacity. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O(2^n) time algorithm for Bin Packing. ...