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)
BlockStructured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
We consider nfold integer programming problems and their generalizations. These are integer linear programming problems for which the linear constraints exhibit a (recursive) blockstructure: The problem decomposes into independent subproblems 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 kchoosable 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 nonempty 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 ZychPawlewicz
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 optimumheight elimination forest. The data structure achieves worstcase …

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 longstanding 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 2Covers 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 allpairs shortest paths algorithm for realweighted 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 polynomialtime 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
Quasipolynomialtime algorithm for Independent Set in P_tfree and C_{>t}free graphs via shrinking the space of connecting subgraphs
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasipolynomialtime algorithm for Maximum Weight Independent Set in P_tfree 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 2Dstrings
The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to twodimensional strings. We consider two types of repetitions in 2Dstrings: 2Druns and quartics (quartics are a 2Dversion …

June 4, 2020, 12:15 p.m.
Kunal Dutta (University of Warsaw)
Dimensionality Reduction for kdistance 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 kdistance, and investigate the effectiveness of dimensionality reduction …

March 26, 2020, 12:15 p.m.
Michał Pilipczuk (University of Warsaw)
Quasipolynomial time approximation schemes for the Maximum Weight Independent Set Problem in Hfree 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 …