Paweł Gawrychowski

research

∙ 04/03/2023

Compressed Indexing for Consecutive Occurrences

The fundamental question considered in algorithms on strings is that of ...

0 Paweł Gawrychowski, et al. ∙

research

∙ 03/13/2023

Optimal Square Detection Over General Alphabets

Squares (fragments of the form xx, for some string x) are arguably the m...

0 Jonas Ellert, et al. ∙

research

∙ 02/02/2023

Optimal Heaviest Induced Ancestors

We revisit the Heaviest Induced Ancestors (HIA) problem that was introdu...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 02/01/2023

Order-Preserving Squares in Strings

An order-preserving square in a string is a fragment of the form uv wher...

0 Paweł Gawrychowski, et al. ∙

research

∙ 07/15/2022

Matching Patterns with Variables Under Edit Distance

A pattern α is a string of variables and terminal letters. We say that α...

0 Paweł Gawrychowski, et al. ∙

research

∙ 03/27/2022

Sublinear Dynamic Interval Scheduling (on one or multiple machines)

We revisit the complexity of the classical Interval Scheduling in the dy...

0 Paweł Gawrychowski, et al. ∙

research

∙ 01/14/2022

Cut query algorithms with star contraction

We study the complexity of determining the edge connectivity of a simple...

0 Simon Apers, et al. ∙

research

∙ 11/09/2021

Pattern Matching on Grammar-Compressed Strings in Linear Time

The most fundamental problem considered in algorithms for text processin...

0 Moses Ganardi, et al. ∙

research

∙ 11/02/2021

Finding the KT partition of a weighted graph in near-linear time

In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near...

0 Simon Apers, et al. ∙

research

∙ 08/25/2021

Faster Exponential Algorithm for Permutation Pattern Matching

The Permutation Pattern Matching problem asks, given two permutations σ ...

0 Paweł Gawrychowski, et al. ∙

research

∙ 06/11/2021

Matching Patterns with Variables under Hamming Distance

A pattern α is a string of variables and terminal letters. We say that α...

0 Paweł Gawrychowski, et al. ∙

research

∙ 05/31/2021

Lower Bounds for the Number of Repetitions in 2D Strings

A two-dimensional string is simply a two-dimensional array. We continue ...

0 Paweł Gawrychowski, et al. ∙

research

∙ 05/13/2021

The Dynamic k-Mismatch Problem

The text-to-pattern Hamming distances problem asks to compute the Hammin...

0 Raphael Clifford, et al. ∙

research

∙ 04/12/2021

The Theory of Universal Graphs for Infinite Duration Games

We introduce the notion of universal graphs as a tool for constructing a...

0 Thomas Colcombet, et al. ∙

research

∙ 03/04/2021

An Almost Optimal Edit Distance Oracle

We consider the problem of preprocessing two strings S and T, of lengths...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 02/23/2021

Conditional Lower Bounds for Variants of Dynamic LIS

In this note, we consider the complexity of maintaining the longest incr...

0 Paweł Gawrychowski, et al. ∙

research

∙ 02/14/2021

Fault-Tolerant Distance Labeling for Planar Graphs

In fault-tolerant distance labeling we wish to assign short labels to th...

0 Aviv Bar-Natan, et al. ∙

research

∙ 01/11/2021

Strictly In-Place Algorithms for Permuting and Inverting Permutations

We revisit the problem of permuting an array of length n according to a ...

0 Bartłomiej Dudek, et al. ∙

research

∙ 11/19/2020

Fully Dynamic Approximation of LIS in Polylogarithmic Time

We revisit the problem of maintaining the longest increasing subsequence...

0 Paweł Gawrychowski, et al. ∙

research

∙ 10/12/2020

Incomplete Directed Perfect Phylogeny in Linear Time

Reconstructing the evolutionary history of a set of species is a central...

0 Giulia Bernardini, et al. ∙

research

∙ 10/01/2020

Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs

Permutation σ appears in permutation π if there exists a subsequence of ...

0 Bartłomiej Dudek, et al. ∙

research

∙ 08/30/2020

Tight Bound for the Number of Distinct Palindromes in a Tree

For an undirected tree with n edges labelled by single letters, we consi...

0 Paweł Gawrychowski, et al. ∙

research

∙ 08/05/2020

A Note on a Recent Algorithm for Minimum Cut

Given an undirected edge-weighted graph G=(V,E) with m edges and n verti...

0 Paweł Gawrychowski, et al. ∙

research

∙ 07/16/2020

Substring Complexity in Sublinear Space

Shannon's entropy is a definitive lower bound for statistical compressio...

0 Giulia Bernardini, et al. ∙

research

∙ 07/12/2020

Efficient Labeling for Reachability in Digraphs

We consider labeling nodes of a directed graph for reachability queries....

0 Maciej Dulęba, et al. ∙

research

∙ 06/03/2020

Dynamic Longest Common Substring in Polylogarithmic Time

The longest common substring problem consists in finding a longest strin...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 05/03/2020

Efficiently Testing Simon's Congruence

Simon's congruence ∼_k is defined as follows: two words are ∼_k-equivale...

0 Paweł Gawrychowski, et al. ∙

research

∙ 03/30/2020

A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

The Longest Common Increasing Subsequence (LCIS) is a variant of the cla...

0 Anadi Agrawal, et al. ∙

research

∙ 03/14/2020

Shorter Labels for Routing in Trees

A routing labeling scheme assigns a binary string, called a label, to ea...

0 Paweł Gawrychowski, et al. ∙

research

∙ 02/13/2020

On Two Measures of Distance between Fully-Labelled Trees

The last decade brought a significant increase in the amount of data and...

0 Giulia Bernardini, et al. ∙

research

∙ 01/16/2020

Generalised Pattern Matching Revisited

In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukris...

0 Bartłomiej Dudek, et al. ∙

research

∙ 01/05/2020

All non-trivial variants of 3-LDT are equivalent

The popular 3-SUM conjecture states that there is no strongly subquadrat...

0 Bartłomiej Dudek, et al. ∙

research

∙ 11/04/2019

Minimum Cut in O(mlog^2 n) Time

We give a randomized algorithm that finds a minimum cut in an undirected...

0 Paweł Gawrychowski, et al. ∙

research

∙ 07/28/2019

Minimal Absent Words in Rooted and Unrooted Trees

We extend the theory of minimal absent words to (rooted and unrooted) tr...

0 Gabriele Fici, et al. ∙

research

∙ 05/07/2019

Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication

An elastic-degenerate (ED) string is a sequence of n sets of strings of ...

0 Giulia Bernardini, et al. ∙

research

∙ 05/03/2019

RLE edit distance in near optimal time

We show that the edit distance between two run-length encoded strings of...

0 Raphael Clifford, et al. ∙

research

∙ 02/12/2019

Compressed Range Minimum Queries

Given a string S of n integers in [0,σ), a range minimum query RMQ(i, j)...

0 Paweł Gawrychowski, et al. ∙

research

∙ 02/06/2019

Top Tree Compression of Tries

We present a compressed representation of tries based on top tree compre...

0 Philip Bille, et al. ∙

research

∙ 12/17/2018

The complexity of mean payoff games using universal graphs

We study the computational complexity of solving mean payoff games. This...

0 Nathanaël Fijalkow, et al. ∙

research

∙ 11/15/2018

Computing Quartet Distance is Equivalent to Counting 4-Cycles

The quartet distance is a measure of similarity used to compare two unro...

0 Bartłomiej Dudek, et al. ∙

research

∙ 11/05/2018

Almost Optimal Distance Oracles for Planar Graphs

We present new tradeoffs between space and query-time for exact distance...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 10/17/2018

Fast and Longest Rollercoasters

For k≥ 3, a k-rollercoaster is a sequence of numbers whose every maximal...

0 Paweł Gawrychowski, et al. ∙

research

∙ 09/07/2018

Streaming dictionary matching with mismatches

In the k-mismatch problem we are given a pattern of length m and a text ...

0 Paweł Gawrychowski, et al. ∙

research

∙ 07/04/2018

Near-Optimal Distance Emulator for Planar Graphs

Given a graph G and a set of terminals T, a distance emulator of G is an...

0 Hsien-Chih Chang, et al. ∙

research

∙ 06/25/2018

Fast entropy-bounded string dictionary look-up with mismatches

We revisit the fundamental problem of dictionary look-up with mismatches...

0 Paweł Gawrychowski, et al. ∙

research

∙ 04/26/2018

Edit Distance between Unrooted Trees in Cubic Time

Edit distance between trees is a natural generalization of the classical...

0 Bartłomiej Dudek, et al. ∙

research

∙ 02/15/2018

A Faster FPTAS for #Knapsack

Given a set W = {w_1,..., w_n} of non-negative integer weights and an in...

0 Paweł Gawrychowski, et al. ∙

research

∙ 01/03/2018

Slowing Down Top Trees for Better Worst-Case Bounds

We consider the top tree compression scheme introduced by Bille et al. [...

0 Bartłomiej Dudek, et al. ∙

Paweł Gawrychowski

Featured Co-authors