Paweł Gawrychowski

teaching and professional activities

• • Currently taught courses: none.

  • Office hours: Thursday 14:15-16:00 online, please send me an email (if I don't respond within a day, please email me again!).

  • I will be the director of ICPC Central Europe Regional Contest 2025 in Wrocław (and I was the director of ICPC Central Europe Regional Contest 2024).

  • Together with Filip Mazowiecki and Michał Skrzypczak, we will chair MFCS 2025. Together with Tatiana Starikovskaya, we chaired CPM 2021 in hybrid mode, and then organised the "New Horizons in Stringology" workshop. I was involved in organising the pre-CPM 2023 summer school, then the pre-CPM 2024 summer school.

  • I gave (or will give) an invited talk at IWOCA 2025, DLT 2024, FIT 2022, LATA 2019, CPM 2019, CiE 2015. Thanks for inviting me!

  • I will be in the program committee of ICALP 2026, SOSA 2026, SPIRE 2025. I was in the program committee of WADS 2025, IWOCA 2025, CPM 2025, ICALP 2025,  STACS 2025, SPIRE 2024, HALG 2024, ICALP (track A) 2024,  LATIN 2024,  SPIRE 2023, ESA (track A) 2023, CPM 2023, WADS 2023, SPIRE 2022, CPM 2022, ESA (track S) 2022, DCFS 2021, MFCS 2021, CSR 2021, SPIRE 2020, DCFS 2020, LATA 2020&2021, DLT 2020, CiE 2020, SOSA 2020, SPIRE 2019, DLT 2019, CSR 2019, CiE 2019, SOFSEM 2019, CPM 2018, STACS 2018, SPIRE 2017, MFCS 2017, SPIRE 2016, ESA 2016, CPM 2016, SPIRE 2015 and CPM 2013.

  • I have a blog where I used to write about interesting algorithmic puzzles (in Polish). I organised a programming competition called Wielka Przesmycka for 10 years but this seems to be over.

preprints & to appear

• • Paweł Gawrychowski, Wojciech Janczewski: Conditional Lower Bounds for Variants of Dynamic LIS (arxiv)

  • Paweł Gawrychowski, Adam Górkiewicz: Better Indexing for Rectangular Pattern matching, to appear in ESA 2025

  • Paweł Gawrychowski, Egor Gorbachev, Tomasz Kociumaka: Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications, to appear in ESA 2025 (arxiv)

theses

• • Paweł Gawrychowski: Pattern matching in compressed text, my PhD thesis (pdf) (slides from the defense)

publications

• Jonas Ellert, Paweł Gawrychowski, Adam Górkiewicz, Tatiana Starikovskaya: Faster two-dimensional pattern matching with k mismatches, SODA 2025 (arxiv)

• Paweł Gawrychowski, Florin Manea and Markus L. Schmid: Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration, PODS 2025 (arxiv)

• Paweł Gawrychowski, Mateusz Wasylkiewicz: Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity, ESA 2024 (track S) (arxiv)

• Bartłomiej Dudek, Paweł Gawrychowski: Online Context-Free Recognition in OMv Time, CPM 2024

• Philip Bille, Paweł Gawrychowski, Inge Li Gørtz and Simon R. Tarnow: Faster Sliding Window String Indexing in Streams, CPM 2024

• Panagiotis Charalampopoulos, Paweł Gawrychowski, Samah Ghazawi: Optimal bound for distinct quartics, ICALP 2024 (arxiv)

• Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner: Compressed consecutive pattern matching, DCC 2024 (hal)

• Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya: Sorting Signed Permutations by Reversals in Nearly-Linear Time, SOSA@SODA 2024 (arixv)

• Giulia Bernardini, Gabriele Fici, Paweł Gawrychowski, Solon P. Pissis: Substring Complexity in Sublinear Space, ISAAC 2023 (arxiv)

• Paweł Gawrychowski, Maria Kosche, Florin Manea: On the Number of Factors in the LZ-End Factorization, SPIRE 2023

• Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya and Teresa Anna Steiner: Compressed Indexing for Consecutive Occurrences, CPM 2023

• Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski and Karol Pokorski: Optimal Heaviest Induced Ancestors, CPM 2023 (arxiv)

• Paweł Gawrychowski, Samah Ghazawi and Gad M. Landau: Order-Preserving Squares in Strings, CPM 2023 (arxiv)

• Jonas Ellert, Paweł Gawrychowski, Garance Gourdel: Optimal Square Detection Over General Alphabets, SODA 2023 (arxiv)

• Simon Apers, Yuval Efron, Paweł Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai: Cut query algorithms with star contraction, FOCS 2022 (arxiv)

• Simon Apers, Paweł Gawrychowski, Troy Lee: Finding the KT partition of a weighted graph in near-linear time, APPROX 2022 (arxiv)

• Paweł Gawrychowski, Florin Manea, Stefan Siemer: Matching Patterns with Variables Under Edit Distance, SPIRE 2022

• Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann: On the Hardness of Computing the Edit Distance of Shallow Trees, SPIRE 2022:

• Paweł Gawrychowski, Karol Pokorski: Sublinear Dynamic Interval Scheduling (on one or multiple machines), ICALP 2022 (arxiv)

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

• • Museum

  • Justice for all

  • Cardsharper

Sometimes I write articles about interesting problems from such contests. Unfortunately, most (all?) of this stuff is in Polish.

• Wielka Przesmycka Revolutions 2012 - solutions

• Wielka Przesmycka Reloaded 2011 - solutions

  • My favourite task (well, one of them, actually)

• My blog

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.

• • UVa (you need to be logged in)

  • acm.sgu.ru

  • TopCoder

• Timus