Organizatorzy

dr hab. Michał Pilipczuk, prof. UW

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

29 listopada 2024 14:15
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 …
22 listopada 2024 14:15
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 …
15 listopada 2024 14:15
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 …
8 listopada 2024 14:15
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. …
25 października 2024 14:15
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 …
18 października 2024 14:15
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 …
29 kwietnia 2021 12:15
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 …
15 kwietnia 2021 12:15
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 …
1 kwietnia 2021 12:15
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 -> …
18 marca 2021 12:15
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 …
4 marca 2021 12:15
Ł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 …
21 stycznia 2021 12:15
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 …
7 stycznia 2021 12:15
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 …
17 grudnia 2020 12:15
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 …
3 grudnia 2020 12:15
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 …