Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. ucz.

Information

Home page

List of talks

• 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 …

  ---

• Jan. 16, 2020, 12:15 p.m.
  Kunal Dutta (MIM UW)
  Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets
  Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in …

  ---

• Jan. 9, 2020, 12:15 p.m.
  Panagiotis Charalampopoulos (King's College London and University of Warsaw)
  Almost Optimal Distance Oracles for Planar Graphs
  We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors …

  ---

• Dec. 19, 2019, 12:15 p.m.
  Jakub Łącki (Google Research NY)
  Massively parallel algorithms for finding connected components
  In this talk we consider the problem of finding connected components in a distributed setting. We present state of the art algorithms that achieve near-optimal round complexity and work well in practice. Our main focus …

  ---