Czekaj...Wczytywanie... Nie jesteś zalogowany | zaloguj się

## Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

• Skala szarości
• Wysoki kontrast
• Negatyw
• Reset

# Seminarium "Algorytmika"

Research seminar (FRIDAYS, usually biweekly at 14.15 in room 5060 or online)

For schedule or link to online meetings, see https://semalgo.wordpress.com/

Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf

5060

## Strona domowa

https://semalgo.wordpress.com/

## Lista referatów

• 2020-11-05, godz. 12:15, online

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 with large pathwidth has large treewidth or contains a subdivision...

• 2020-10-22, godz. 12:15, online

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 runs in time n^O(log^3(n)), where t is assumed to ...

• 2020-10-08, godz. 12:15, [online seminar]

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 of squares in standard strings). Amir et al. introduced...

• 2020-06-04, godz. 12:15, zoom

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 for this problem. Our main result answers an open question of Sheehy [Proc. SoCG, 2014], s...

• 2020-03-26, godz. 12:15, 5870

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 nonadjacent vertices in a given graph with the maximum possible cardinali...

• 2020-01-16, godz. 12:15, 5870

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 theory and in practice. Randomized incremental constructions ...

• 2020-01-09, godz. 12:15, 5870

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 from the naive linear space, constant ...

• 2019-12-19, godz. 12:15, 5870

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 is the Massively Parallel Computation (MPC) model, which is the standard theo...

• 2019-12-12, godz. 12:15, 5870

Erik Jan van Leeuwen (Utrecht University)

On Geometric Set Cover for Orthants

We study Set Cover for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from...

• 2019-11-28, godz. 12:15, 5870

Petteri Kaski (Department of Computer Science, Aalto University)

Probabilistic tensors and opportunistic Boolean matrix multiplication

We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under tak...