e-mail: gawry [at] cs.uni.wroc.pl, download my PGP key

I'm an associate professor at University of Wrocław. I received my PhD from University of Wrocław in October 2011. Then I have spent three years at Max Planck Institute in Saarbrücken, year and a half as a post-doc at University of Warsaw supported by Warsaw Center of Mathematics and Computer Science, and then another year and a half at University of Haifa, all while on a leave of absence from University of Wrocław. I am mainly interested in data structures with applications to string processing.

teaching and professional activities

See here for the list of courses I have taught (mostly in Polish).

preprints & to appear

  • Simon Apers, Yuval Efron, Paweł Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai: Cut query algorithms with star contraction, to appear in FOCS 2022 (arxiv)
  • Paweł Gawrychowski, Wojciech Janczewski: Conditional Lower Bounds for Variants of Dynamic LIS (arxiv)
  • Simon Apers, Paweł Gawrychowski, Troy Lee: Finding the KT partition of a weighted graph in near-linear time, to appear in APPROX 2022 (arxiv)
  • Paweł Gawrychowski, Karol Pokorski: Sublinear Dynamic Interval Scheduling (on one or multiple machines), to appear in ICALP 2022 (arxiv)

theses

publications

  • Raphael Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel Martin, and Przemysław Uznański: The Dynamic k-Mismatch Problem, CPM 2022 (arxiv) Best Paper Award
  • Moses Ganardi, Paweł Gawrychowski: Pattern Matching on Grammar-Compressed Strings in Linear Time, SODA 2022 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya: Streaming Regular Expression Membership and Pattern Matching, SODA 2022
  • Paweł Gawrychowski, Mateusz Rzepecki: Faster Exponential Algorithm for Permutation Pattern Matching, SOSA@SODA 2022 (arxiv)
  • Paweł Gawrychowski, Wojciech Janczewski: Simpler Adjacency Labeling for Planar Graphs with B-Trees, SOSA@SODA 2022
  • Paweł Gawrychowski, Florin Manea, Stefan Siemer: Matching Patterns with Variables under Hamming Distance, MFCS 2021 (arxiv)
  • Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau: Lower Bounds for the Number of Repetitions in 2D Strings, SPIRE 2021 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski: Strictly In-Place Algorithms for Permuting and Inverting Permutations, WADS 2021 (arxiv)
  • Giulia Bernardini, Paola Bonizzoni, Paweł Gawrychowski: Incomplete Directed Perfect Phylogeny in Linear Time, WADS 2021 (arxiv)
  • Paweł Gawrychowski, Przemysław Uznański: Better distance labeling for unweighted planar graphs, WADS 2021 (earlier arxiv version) Best Paper Award
  • Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann: Fault-Tolerant Distance Labeling for Planar Graphs, SIROCCO 2021 (arxiv)
  • Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann: An Almost Optimal Edit Distance Oracle, ICALP 2021 (arxiv)
  • Paweł Gawrychowski, Wojciech Janczewski: Fully Dynamic Approximation of LIS in Polylogarithmic Time, STOC 2021 (arxiv)
  • Paweł Gawrychowski, Maria Kosche, Tore Koss, Florin Manea, Stefan Siemer: Efficiently Testing Simon's Congruence, STACS 2021 (arxiv)
  • Paweł Gawrychowski, Shay Mozes, Oren Weimann: A Note on a Recent Algorithm for Minimum Cut, SOSA@SODA 2021 (arxiv)
  • Paweł Gawrychowski, Wojciech Janczewski, Jakub Łopuszański: Shorter Labels for Routing in Trees, SODA 2021 (arxiv)
  • Paweł Gawrychowski, Shay Mozes, Oren Weimann: Planar Negative k-Cycle, SODA 2021
  • Anadi Agrawal, Paweł Gawrychowski: A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, ISAAC 2020 (arxiv)
  • Maciej Dulęba, Pawel Gawrychowski, Wojciech Janczewski: Efficient Labeling for Reachability in Digraphs, ISAAC 2020 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski: Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs, ISAAC 2020 Best Paper Award
  • Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann:
 The complexity of mean payoff games using universal graphs, MFCS 2020 (arxiv)
  • Paweł Gawrychowski, Shay Mozes and Oren Weimann: Minimum Cut in O(m log^2 n) Time, ICALP 2020 Best Paper Award
  • Panagiotis Charalampopoulos, Paweł Gawrychowski and Karol Pokorski: Dynamic Longest Common Substring in Polylogarithmic Time, ICALP 2020 (arxiv)
  • Paweł Gawrychowski, Samah Ghazawi and Gad M. Landau: On Indeterminate Strings Matching, CPM 2020
  • Giulia Bernardini, Paola Bonizzoni and Pawel Gawrychowski: On Two Measures of Distance between Fully-Labelled Trees, CPM 2020 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya: All non-trivial variants of 3-LDT are equivalent, STOC 2020 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya: Generalised Pattern Matching Revisited, STACS 2020 (arxiv)
  • Paweł Gawrychowski, Narad Rampersad, Jeffrey Shallit, Marek Szykuła: Existential universality, STACS 2020 (arxiv)
  • Philip Bille, Inge Li Gørtz, Paweł Gawrychowski, Gad M. Landau, Oren Weimann: Top Tree Compression of Tries, ISAAC 2019 (arxiv)
  • Gabriele Fici, Paweł Gawrychowski: Minimal Absent Words in Rooted and Unrooted Trees, SPIRE 2019 (arxiv)
  • Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemysław Uznański: RLE Edit Distance in Near Optimal Time, MFCS 2019
  • Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti, Solon Pissis, Giovanna Rosone: Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication, ICALP 2019
  • Paweł Gawrychowski, Tatiana Starikovskaya: Streaming dictionary matching with mismatches, CPM 2019 (arxiv)
  • Paweł Gawrychowski, Jakub Radoszewski,  Tatiana Starikovskaya: Quasi-Periodicity in Streams, CPM 2019
  • Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann: Almost Optimal Distance Oracles for Planar Graphs, STOC 2019 (arxiv)
  • Bartłomiej Dudek, Pawel Gawrychowski: Computing Quartet Distance is Equivalent to Counting 4-Cycles, STOC 2019 (arxiv)
  • Paweł Gawrychowski, Florin Manea, Radosław Serafin: Fast and Longest Rollercoasters, STACS 2019 (arxiv)
  • Paweł Gawrychowski, Gad M. Landau, Tatiana Starikovskaya: Fast entropy-bounded string dictionary look-up with mismatches, MFCS 2018 (arxiv)
  • Michał Gańczorz, Paweł Gawrychowski, Artur Jeż, Tomasz Kociumaka: Edit Distance with Block Operations, ESA 2018 
  • Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, Oren Weimann: Near-Optimal Distance Emulator for Planar Graphs, ESA 2018 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski: Slowing Down Top Trees for Better Worst-Case Bounds, CPM 2018 (arxiv)
  • Paweł Gawrychowski, Przemysław Uznański: Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance, ICALP 2018
  • Paweł Gawrychowski, Liran Markin, Oren Weimann: A Faster FPTAS for #Knapsack, ICALP 2018 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski: Edit Distance between Unrooted Trees in Cubic Time, ICALP 2018 (arxiv)
  • Paweł Gawrychowski, Adam Karczmarz: Improved Bounds for Shortest Paths in Dense Distance Graphs, ICALP 2018 (arxiv)
  • Paweł Gawrychowski, Gad M. Landau, Wing-Kin Sung, Oren Weimann: A Faster Construction of Greedy Consensus Trees, ICALP 2018 (arxiv)
  • Paweł Gawrychowski, Fabian Kuhn, Jakub Łopuszański, Konstantinos Panagiotou and Pascal Su: Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees, SODA 2018 (arxiv) (presentation)
  • Paweł Gawrychowski, Shay Mozes, Oren Weimann, Christian Wulff-Nielsen: Better Tradeoffs for Exact Distance Oracles in Planar Graphs, SODA 2018 (arxiv) (presentation)
  • Amir Abboud, Paweł Gawrychowski, Shay Mozes, Oren Weimann: Near-Optimal Compression for the Planar Graph Metric, SODA 2018 (arxiv)
  • Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann: Voronoi diagrams on planar graphs, and computing the diameter in deterministic ~O(n5/3) time, SODA 2018 (arxiv)
  • Karl Bringmann, Paweł Gawrychowski, Shay Mozes, Oren Weimann: Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can), SODA 2018 (arxiv)
  • Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki, Piotr Sankowski: Optimal dynamic strings, SODA 2018 (arxiv)
  • Mika Amit, Paweł Gawrychowski: Distinct Squares in Circular Words, SPIRE 2017 (arxiv)
  • Paweł Gawrychowski, Nadav Krasnopolsky, Shay Mozes, Oren Weimann: Dispersion on Trees, ESA 2017 (arxiv)
  • Paweł Gawrychowski, Patrick K. Nicholson: Optimal Query Time for Encoding Range Majority, WADS 2017 (arxiv)
  • Bartłomiej Dudek, Paweł Gawrychowski, Piotr Ostropolski-Nalewaja: A family of approximation algorithms for the maximum duo-preservation string mapping problem, CPM 2017 (arxiv)
  • Paweł Gawrychowski, Pat Nicholson: Optimal Query Time for Encoding Range Majority, WADS 2017 (arxiv)
  • Ofer Freedman, Pawel Gawrychowski, Patrick K. Nicholson, Oren Weimann: Optimal Distance Labeling Schemes for Trees, PODC 2017 (arxiv)
  • Paweł Gawrychowski, Tomasz Kociumaka: Sparse suffix tree construction in optimal time and space, SODA 2017 (arxiv)
  • Dominik D. Freydenberger, Paweł Gawrychowski, Juhani Karhumäki, Florin Manea, Wojciech Rytter: Testing k-binomial equivalence, Multidisciplinary Creativity: homage to Gheorghe Pӑun on his 65th birthday (arxiv)
  • Patrick Hagge Cording, Paweł Gawrychowski, Oren Weimann: Bookmarks in Grammar-Compressed Strings, SPIRE 2016
  • Paweł Gawrychowski, Artur Jeż: LZ77 factorisation of trees, FSTTCS 2016
  • Paweł Gawrychowski, Łukasz Zatorski: Speeding up Dynamic Programming in the Line-Constrained k-median, IWOCA 2016
  • Paweł Gawrychowski, Adrian Kosowski, and Przemysław Uznański: Sublinear-Space Distance Labeling using Hubs, DISC 2016 (arxiv)
  • Paweł Gawrychowski, Gad M. Landau, Shay Mozes and Oren Weimann: The Nearest Colored Node in a Tree, CPM 2016
  • Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Waleń: Faster Longest Common Extension Queries in Strings over General Alphabets, CPM 2016 (arxiv)
  • Paweł Gawrychowski, Oleg Merkurev, Arseny Shur and Przemysław Uznański: Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams, CPM 2016
  • Pawel Gawrychowski, Jukka Suomela and Przemysław Uznański: Randomized algorithms for finding a majority element, SWAT 2016 (arxiv)
  • Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl and Florin Manea: Efficiently Finding All Maximal α-gapped Repeats, STACS 2016
  • Paweł Gawrychowski, Damian Straszak: Strong inapproximability of the shortest reset word, MFCS 2015 (arxiv) (presentation) Best Paper Award
  • Jérémie Chalopin, Shantanu Das, Pawel Gawrychowski, Adrian Kosowski, Arnaud Labourel and Przemysław Uznański: Lock-in Problem for Parallel Rotor-router Walks, DISC 2015 (arxiv)
  • Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter and Tomasz Waleń: Tight Bound for the Number of Distinct Palindromes in a Tree, SPIRE 2015
  • Paweł Gawrychowski, Gregory Kucherov, Benjamin Sach and Tatiana Starikovskaya: Computing the Longest Unbordered Substring, SPIRE 2015
  • Johannes Fischer, Travis Gagie, Paweł Gawrychowski, Tomasz Kociumaka: Approximating LZ77 via Small-Space Multiple-Pattern Matching, ESA 2015 (arxiv)
  • Paweł Gawrychowski, Florin Manea: Longest α-gapped Repeat and Palindrome, FCT 2015
  • Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń: Fast universal reconstruction of a string, WADS 2015 (preliminary version)
  • Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann: Longest common extensions in trees, CPM 2015 (arxiv) (presentation)
  • Paweł Gawrychowski, Shay Mozes, Oren Weimann: Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search, ICALP 2015 (arxiv)
  • Paweł Gawrychowski, Patrick K. Nicholson: Optimal Encodings for Range Min-Max and Top-k, ICALP 2015 (arxiv)
  • Paweł Gawrychowski, Patrick K. Nicholson: Encodings of Range Maximum-Sum Segment Queries and Applications, CPM 2015 (arxiv)
  • Johannes Fischer, Paweł Gawrychowski: Alphabet-dependent string searching with exponential search trees, CPM 2015 (arxiv) (presentation)
  • Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Alberto Ordóñez, Simon J. Puglisi, Yasuo Tabei: Queries on LZ-bounded encodings, DCC 2015 (arxiv)
  • Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya: Wavelet trees meet suffix trees, SODA 2015 (arxiv)
  • Paweł Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson: Weighted ancestors in suffix trees, ESA 2014 (arxiv) (link to PDF)
  • Paweł Gawrychowski, Damian Rusak: Euclidean TSP with few inner points in linear space, ISAAC 2014 (arxiv)
  • Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya: Computing minimal and maximal suffixes revisited, CPM 2014 (arxiv)
  • Paweł Gawrychowski, Przemysław Uznański: Order-preserving pattern matching with k mismatches, CPM 2014 (arxiv)
  • Paweł Gawrychowski, Shay Mozes, Oren Weimann: Improved submatrix maximum queries in Monge matrices, ICALP 2014 (arxiv)
  • Paweł Gawrychowski, Florin Manea, and Dirk Nowotka: Testing generalised freeness in words, STACS 2014 (link to PDF)
  • Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and Simon Puglisi: LZ77-Based Self-Indexing with Faster Pattern Matching, LATIN 2014 (link to PDF)
  • Paweł Gawrychowski, Damian Straszak: Beating O(nm) in approximate LZW-compressed pattern matching, ISAAC 2013 (arxiv) (link to PDF)
  • Paweł Gawrychowski, Gregory Kucherov, Yakov Nekrich and Tatiana Starikovskaya: Minimal discriminating words problem revisited, SPIRE 2013 (link to PDF)
  • Travis Gagie, Paweł Gawrychowski, Yakov Nekrich: Heaviest induced ancestors and longest common substrings, CCCG 2013 (arxiv)
  • Hideo Bannai, Paweł Gawrychowski, Shunsuke Inenaga, and Masayuki Takeda: Converting SLP to LZ78 in almost linear time, CPM 2013 (preliminary version) (link to PDF)
  • Paweł Gawrychowski, Florin Manea, Dirk Nowotka: Discovering hidden repetitions in words, CiE 2013 (link to PDF) 
  • Paweł Gawrychowski: Alphabetic minimax trees in linear time, CSR 2013 (preliminary version) (link to PDF)
  • Paweł Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka, and Catalin Tiseanu: Finding pseudo-repetitions, STACS 2013 (link to PDF)
  • Paweł Gawrychowski: Faster algorithm for computing the edit distance between SLP-compressed strings, SPIRE 2012 (preliminary version) (link to PDF) (presentation)
  • Paweł Gawrychowski: (Really) Tight bounds for dispatching binary methods, (preliminary version)
  • Paweł Gawrychowski: Simple and efficient LZW-compressed multiple pattern matching, CPM 2012 (preliminary version) (presentation) Best Student Paper Award
  • Travis Gagie, Paweł  Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, Simon J. Puglisi: A faster grammar-based self-index, LATA 2012 (arxiv) (link to PDF) (presentation)
  • Paweł Gawrychowski: Tying up the loose ends in fully LZW-compressed pattern matching, STACS 2012 (arxiv) (presentation)
  • Travis Gagie, Paweł Gawrychowski, Simon J. Puglisi: Faster approximate pattern matching in compressed repetitive texts, ISAAC 2011 (arxiv)
  • Paweł Gawrychowski, Artur Jeż, Andreas Maletti: On minimising automata with errors, MFCS 2011 (arxiv) (presentation)
  • Paweł Gawrychowski: Chrobak normal form revisited, with applications, CIAA 2011 (preliminary full version) (presentation) Best Paper Award
  • Paweł Gawrychowski: Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic, ESA 2011 (arxiv) (presentation) Best Student Paper Award, invited to the special issue of Algorithmica (preliminary journal version)
  • Paweł Gawrychowski: Optimal pattern matching in LZW compressed strings, SODA 2011 (conference version) (presentation), full version in the special issue of ACM Transactions on Algorithms (preliminary journal version) (link to PDF)
  • Paweł Gawrychowski, Artur Jeż, Łukasz Jeż: Validating the Knuth-Morris-Pratt failure function, fast and online, CSR 2010 (link to PDF)
  • Travis Gagie, Paweł Gawrychowski: Grammar-based compression in a streaming model, LATA 2010 (arxiv) (link to PDF)
  • Paweł Gawrychowski, Marin Gutan, Andrzej Kisielewicz: On the problem of freenes of multiplicative matrix semigroups, Theoretical Computer Science 411 (2010) 1115-1120 (link to PDF)
  • Paweł Gawrychowski, Artur Jeż: Hyper-minimisation made efficient, MFCS 2009 (link to PDF) Best Student Paper Award
  • Paweł Gawrychowski, Travis Gagie: Minimax trees in linear time with applications, IWOCA 2009 (arXiv) tied for Best Student Paper Award
  • Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit: Finding the growth rate of a regular or context-free language in polynomial time, DLT 2008 (link to PDF) (presentation), full version published in International Journal of Foundations of Computer Science 21:4 (2010) 597-618 (journal version)
  • Jarosław Byrka, Paweł Gawrychowski, Steven Kelk, Katharina T. Huber: Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks, Journal of Discrete Algorithms volume 8:1 (2010) 65-75 (arXiv) (journal version)
  • Paweł Gawrychowski, Andrzej Kisielewicz: 2-synchronizing words, LATA 2008 (link to PDF) (presentation)
  • Alessandra Cherubini, Paweł Gawrychowski, Andrzej Kisielewicz, Brunetto Piochi: A combinatorial approach to collapsing words, MFCS 2006 (link to PDF) (presentation)

trivia

My Erdős number seems to be 2, through Jeff Shallit.

Here you can see a video about me (short, but hey, I'm a rather boring person!).

programming contests

I have spent a lot of time solving (and creating) problems from various programming contests. Here are links to a few tasks that I have set (I'm a terrible story teller so the statements have usually been created by someone else) and still find interesting: Sometimes I write articles about interesting problems from such contests. Unfortunately, most (all?) of this stuff is in Polish.
Here are a few statistics from my problem solving days. Feel free to ask if you are stuck with a problem that I have solved.