Research seminar (Fridays, at 14.15 in room 5060)
For schedule or link to online meetings, see https://semalgo.wordpress.com/
If you want to get notifications, sign up to the mailing list algorytmy@mimuw.edu.pl
Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf
Google calendar: https://calendar.google.com/calendar/embed?src=q1pbv62cra5jf9satch9ip49ms%40group.calendar.google.com&ctz=Europe%2FWarsaw
YouTube cannel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp
Organizers
- dr hab. Marcin Pilipczuk, prof. UW
Information
Fridays, 2:15 p.m. , room: 5060Home page
https://semalgo.wordpress.com/List of talks
-
April 29, 2021, 12:15 p.m.
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 …
-
April 15, 2021, 12:15 p.m.
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 …
-
April 1, 2021, 12:15 p.m.
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 -> …
-
March 18, 2021, 12:15 p.m.
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 …
-
March 4, 2021, 12:15 p.m.
Ł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 …
-
Jan. 21, 2021, 12:15 p.m.
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 …
-
Jan. 7, 2021, 12:15 p.m.
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 …
-
Dec. 17, 2020, 12:15 p.m.
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 …
-
Dec. 3, 2020, 12:15 p.m.
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 …
-
Nov. 19, 2020, 12:15 p.m.
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, …
-
Nov. 5, 2020, 12:15 p.m.
Wojciech Nadara
Approximating pathwidth for graphs of small treewidth
We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. Our approach builds on the following key insight: every graph …
-
Oct. 22, 2020, 12:15 p.m.
Marcin Pilipczuk
Quasi-polynomial-time algorithm for Independent Set in P_t-free and C_{>t}-free graphs via shrinking the space of connecting subgraphs
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in P_t-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm …
-
Oct. 8, 2020, 12:15 p.m.
Wiktor Zuba
The number of repetitions in 2D-strings
The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-strings: 2D-runs and quartics (quartics are a 2D-version …
-
June 4, 2020, 12:15 p.m.
Kunal Dutta (University of Warsaw)
Dimensionality Reduction for k-distance Applied to Persistent Homology
Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction …
-
March 26, 2020, 12:15 p.m.
Michał Pilipczuk (University of Warsaw)
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
This Thursday we will have our first virtual algorithms seminar! Please join us at https://us04web.zoom.us/j/967084831 (Meeting ID: 967 084 831). In the Maximum Independent Set problem we are asked to find a set of pairwise …