Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. UW

Information

Home page

List of talks

• Nov. 29, 2024, 2:15 p.m.
  Marcin Pilipczuk
  Bounding ε-scatter dimension via metric sparsity
  A recent work of Abbasi et al. [FOCS 2023] introduced the notion of ε-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range …

  ---

• Nov. 22, 2024, 2:15 p.m.
  Kunal Dutta
  A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels
  Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, compared to other typical …

  ---

• Nov. 15, 2024, 2:15 p.m.
  Wiktor Zuba
  Space-Efficient Indexes for Uncertain Strings
  Strings in the real world are often encoded with some level of uncertainty, for example, due to: unreliable data measurements; flexible sequence modeling; or noise introduced for privacy protection. In the character-level uncertainty model, an …

  ---

• Nov. 8, 2024, 2:15 p.m.
  Anita Dürr (Max Planck Institute for Informatics)
  Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
  We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time ˜O(n + t√pmax), where n is the number of items, t is the knapsack capacity, and pmax is the maximum item profit. …

  ---

• Oct. 25, 2024, 2:15 p.m.
  Maël Dumas
  On graphs coverable by k shortest paths
  We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single exponential function of k. As …

  ---

• Oct. 18, 2024, 2:15 p.m.
  Konrad Majewski
  Parameterized Dynamic Data Structure for Split Completion
  We design a randomized data structure that, for a fully dynamic graph G updated by edge insertions and deletions and integers k, d fixed upon initialization, maintains the answer to the Split Completion problem: whether …

  ---

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

  ---