Pawel Gawrychowski
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
133
Venues
21
Active years
2006–2026
Best venue rank
A*
Where they publish
Papers
133 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | CPM | Balancing Two-Dimensional Straight-Line Programs. | Itai Boneh, Estban Gabory, Pawel Gawrychowski, Adam Grkiewicz |
| 2026 | CPM | Optimal Structure for Prefix-Substring Queries. | Pawel Gawrychowski, Florin Manea, Jonas Richardsen |
| 2026 | ESA | String Matching in (Block) Graphs: A Full Classification by Walk Length. | Sebastian Angrick, Ben Bals, Pawel Gawrychowski, Solon P. Pissis, Yuki Yonemoto |
| 2026 | ESA | Online Approximate Circular Pattern Matching in Small Space. | Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Pawel Gawrychowski, Tatiana Starikovskaya |
| 2026 | ESA | Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries. | Pawel Gawrychowski, Adam Grkiewicz, Srinivasa Rao Satti |
| 2026 | ICALP | Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms. | Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Pawel Gawrychowski, Tatiana Starikovskaya |
| 2025 | CPM | Minimal Generators in Optimal Time. | Jonas Ellert, Pawel Gawrychowski, Tatiana Starikovskaya |
| 2025 | CPM | Faster Approximate Elastic-Degenerate String Matching - Part B. | Pawel Gawrychowski, Adam Grkiewicz, Pola Marciniak, Solon P. Pissis, Karol Pokorski |
| 2025 | ESA | Better Indexing for Rectangular Pattern Matching. | Pawel Gawrychowski, Adam Grkiewicz |
| 2025 | ESA | Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. | Pawel Gawrychowski, Egor Gorbachev, Tomasz Kociumaka |
| 2025 | ICALP | Optimal Distance Labeling for Permutation Graphs. | Pawel Gawrychowski, Wojciech Janczewski |
| 2025 | SODA | Faster two-dimensional pattern matching with | Jonas Ellert, Pawel Gawrychowski, Adam Grkiewicz, Tatiana Starikovskaya |
| 2025 | SPIRE | Two-Player Communication Complexity of Pattern Matching. | Pawel Gawrychowski, Wojciech Janczewski |
| 2024 | CPM | Online Context-Free Recognition in OMv Time. | Bartlomiej Dudek, Pawel Gawrychowski |
| 2024 | CPM | Faster Sliding Window String Indexing in Streams. | Philip Bille, Pawel Gawrychowski, Inge Li Grtz, Simon R. Tarnow |
| 2024 | DCC | Compressed Consecutive Pattern Matching | Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner |
| 2024 | ESA | Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity. | Pawel Gawrychowski, Mateusz Wasylkiewicz |
| 2024 | ICALP | Optimal Bounds for Distinct Quartics. | Panagiotis Charalampopoulos, Pawel Gawrychowski, Samah Ghazawi |
| 2024 | LATIN | Enumerating m-Length Walks in Directed Graphs with Constant Delay. | Duncan Adamson, Pawel Gawrychowski, Florin Manea |
| 2023 | CPM | Optimal Near-Linear Space Heaviest Induced Ancestors. | Panagiotis Charalampopoulos, Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski |
| 2023 | CPM | Order-Preserving Squares in Strings. | Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau |
| 2023 | CPM | Compressed Indexing for Consecutive Occurrences. | Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner |
| 2023 | ISAAC | Substring Complexity in Sublinear Space. | Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski, Solon P. Pissis |
| 2023 | SODA | Optimal Square Detection Over General Alphabets. | Jonas Ellert, Pawel Gawrychowski, Garance Gourdel |
| 2023 | SPIRE | On the Number of Factors in the LZ-End Factorization. | Pawel Gawrychowski, Maria Kosche, Florin Manea |
| 2022 | CPM | The Dynamic k-Mismatch Problem. | Raphal Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski |
| 2022 | FOCS | Cut Query Algorithms with Star Contraction. | Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai |
| 2022 | ICALP | Sublinear Dynamic Interval Scheduling (On One or Multiple Machines). | Pawel Gawrychowski, Karol Pokorski |
| 2022 | SODA | Streaming Regular Expression Membership and Pattern Matching. | Bartlomiej Dudek, Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya |
| 2022 | SODA | Pattern Matching on Grammar-Compressed Strings in Linear Time. | Moses Ganardi, Pawel Gawrychowski |
| 2022 | SPIRE | On the Hardness of Computing the Edit Distance of Shallow Trees. | Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2022 | SPIRE | Matching Patterns with Variables Under Edit Distance. | Pawel Gawrychowski, Florin Manea, Stefan Siemer |
| 2021 | ICALP | An Almost Optimal Edit Distance Oracle. | Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2021 | MFCS | Matching Patterns with Variables Under Hamming Distance. | Pawel Gawrychowski, Florin Manea, Stefan Siemer |
| 2021 | SODA | Shorter Labels for Routing in Trees. | Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski |
| 2021 | SODA | Planar Negative | Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2021 | STOC | Fully dynamic approximation of LIS in polylogarithmic time. | Pawel Gawrychowski, Wojciech Janczewski |
| 2021 | STACS | Efficiently Testing Simon's Congruence. | Pawel Gawrychowski, Maria Kosche, Tore Ko, Florin Manea, Stefan Siemer |
| 2021 | SIROCCO | Fault-Tolerant Distance Labeling for Planar Graphs. | Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2021 | SPIRE | Lower Bounds for the Number of Repetitions in 2D Strings. | Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau |
| 2021 | WADS | Incomplete Directed Perfect Phylogeny in Linear Time. | Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski |
| 2021 | WADS | Strictly In-Place Algorithms for Permuting and Inverting Permutations. | Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski |
| 2021 | WADS | Better Distance Labeling for Unweighted Planar Graphs. | Pawel Gawrychowski, Przemyslaw Uznanski |
| 2020 | CPM | On Two Measures of Distance Between Fully-Labelled Trees. | Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski |
| 2020 | CPM | On Indeterminate Strings Matching. | Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau |
| 2020 | ICALP | Dynamic Longest Common Substring in Polylogarithmic Time. | Panagiotis Charalampopoulos, Pawel Gawrychowski, Karol Pokorski |
| 2020 | ICALP | Minimum Cut in O(m log² n) Time. | Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2020 | ISAAC | Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. | Bartlomiej Dudek, Pawel Gawrychowski |
| 2020 | ISAAC | A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem. | Anadi Agrawal, Pawel Gawrychowski |
| 2020 | ISAAC | Efficient Labeling for Reachability in Directed Acyclic Graphs. | Maciej Duleba, Pawel Gawrychowski, Wojciech Janczewski |
| 2020 | MFCS | Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. | Nathanal Fijalkow, Pawel Gawrychowski, Pierre Ohlmann |
| 2020 | STOC | All non-trivial variants of 3-LDT are equivalent. | Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya |
| 2020 | STACS | Generalised Pattern Matching Revisited. | Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya |
| 2020 | STACS | Existential Length Universality. | Pawel Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey O. Shallit, Marek Szykula |
| 2019 | CPM | How to Exploit Periodicity (Invited Talk). | Pawel Gawrychowski |
| 2019 | CPM | Quasi-Periodicity in Streams. | Pawel Gawrychowski, Jakub Radoszewski, Tatiana Starikovskaya |
| 2019 | CPM | Streaming Dictionary Matching with Mismatches. | Pawel Gawrychowski, Tatiana Starikovskaya |
| 2019 | ICALP | Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication. | Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone |
| 2019 | ISAAC | Top Tree Compression of Tries. | Philip Bille, Pawel Gawrychowski, Inge Li Grtz, Gad M. Landau, Oren Weimann |
| 2019 | MFCS | RLE Edit Distance in Near Optimal Time. | Raphal Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski |
| 2019 | STOC | Almost optimal distance oracles for planar graphs. | Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2019 | STOC | Computing quartet distance is equivalent to counting 4-cycles. | Bartlomiej Dudek, Pawel Gawrychowski |
| 2019 | STACS | Fast and Longest Rollercoasters. | Pawel Gawrychowski, Florin Manea, Radoslaw Serafin |
| 2019 | SPIRE | Minimal Absent Words in Rooted and Unrooted Trees. | Gabriele Fici, Pawel Gawrychowski |
| 2018 | CPM | Slowing Down Top Trees for Better Worst-Case Compression. | Bartlomiej Dudek, Pawel Gawrychowski |
| 2018 | ESA | Near-Optimal Distance Emulator for Planar Graphs. | Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2018 | ESA | Edit Distance with Block Operations. | Michal Ganczorz, Pawel Gawrychowski, Artur Jez, Tomasz Kociumaka |
| 2018 | ICALP | Edit Distance between Unrooted Trees in Cubic Time. | Bartlomiej Dudek, Pawel Gawrychowski |
| 2018 | ICALP | Improved Bounds for Shortest Paths in Dense Distance Graphs. | Pawel Gawrychowski, Adam Karczmarz |
| 2018 | ICALP | A Faster Construction of Greedy Consensus Trees. | Pawel Gawrychowski, Gad M. Landau, Wing-Kin Sung, Oren Weimann |
| 2018 | ICALP | A Faster FPTAS for #Knapsack. | Pawel Gawrychowski, Liran Markin, Oren Weimann |
| 2018 | ICALP | Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance. | Pawel Gawrychowski, Przemyslaw Uznanski |
| 2018 | MFCS | Fast Entropy-Bounded String Dictionary Look-Up with Mismatches. | Pawel Gawrychowski, Gad M. Landau, Tatiana Starikovskaya |
| 2018 | SODA | Near-Optimal Compression for the Planar Graph Metric. | Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2018 | SODA | Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). | Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2018 | SODA | Optimal Dynamic Strings. | Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, Piotr Sankowski |
| 2018 | SODA | Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees. | Pawel Gawrychowski, Fabian Kuhn, Jakub Lopuszanski, Konstantinos Panagiotou, Pascal Su |
| 2018 | SODA | Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic | Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann |
| 2018 | SODA | Better Tradeoffs for Exact Distance Oracles in Planar Graphs. | Pawel Gawrychowski, Shay Mozes, Oren Weimann, Christian Wulff-Nilsen |
| 2017 | CPM | A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem. | Bartlomiej Dudek, Pawel Gawrychowski, Piotr Ostropolski-Nalewaja |
| 2017 | ESA | Dispersion on Trees. | Pawel Gawrychowski, Nadav Krasnopolsky, Shay Mozes, Oren Weimann |
| 2017 | PODC | Optimal Distance Labeling Schemes for Trees. | Ofer Freedman, Pawel Gawrychowski, Patrick K. Nicholson, Oren Weimann |
| 2017 | SODA | Sparse Suffix Tree Construction in Optimal Time and Space. | Pawel Gawrychowski, Tomasz Kociumaka |
| 2017 | SPIRE | Distinct Squares in Circular Words. | Mika Amit, Pawel Gawrychowski |
| 2017 | WADS | Optimal Query Time for Encoding Range Majority. | Pawel Gawrychowski, Patrick K. Nicholson |
| 2016 | CPM | Faster Longest Common Extension Queries in Strings over General Alphabets. | Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen |
| 2016 | CPM | The Nearest Colored Node in a Tree. | Pawel Gawrychowski, Gad M. Landau, Shay Mozes, Oren Weimann |
| 2016 | CPM | Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. | Pawel Gawrychowski, Oleg Merkurev, Arseny M. Shur, Przemyslaw Uznanski |
| 2016 | IWOCA | Speeding up Dynamic Programming in the Line-Constrained k-median. | Pawel Gawrychowski, Lukasz Zatorski |
| 2016 | PODC | Brief Announcement: Sublinear-Space Distance Labeling Using Hubs. | Pawel Gawrychowski, Adrian Kosowski, Przemyslaw Uznanski |
| 2016 | STACS | Efficiently Finding All Maximal alpha-gapped Repeats. | Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Kppl, Florin Manea |
| 2016 | SPIRE | Bookmarks in Grammar-Compressed Strings. | Patrick Hagge Cording, Pawel Gawrychowski, Oren Weimann |
| 2015 | CPM | Alphabet-Dependent String Searching with Wexponential Search Trees. | Johannes Fischer, Pawel Gawrychowski |
| 2015 | CPM | Longest Common Extensions in Trees. | Philip Bille, Pawel Gawrychowski, Inge Li Grtz, Gad M. Landau, Oren Weimann |
| 2015 | CPM | Encodings of Range Maximum-Sum Segment Queries and Applications. | Pawel Gawrychowski, Patrick K. Nicholson |
| 2015 | DCC | Queries on LZ-Bounded Encodings. | Djamal Belazzougui, Travis Gagie, Pawel Gawrychowski, Juha Krkkinen, Alberto Ordez Pereira, Simon J. Puglisi, Yasuo Tabei |
| 2015 | ESA | Approximating LZ77 via Small-Space Multiple-Pattern Matching. | Johannes Fischer, Travis Gagie, Pawel Gawrychowski, Tomasz Kociumaka |
| 2015 | FCT | Longest α-Gapped Repeat and Palindrome. | Pawel Gawrychowski, Florin Manea |
| 2015 | ICALP | Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search. | Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2015 | ICALP | Optimal Encodings for Range Top- k k , Selection, and Min-Max. | Pawel Gawrychowski, Patrick K. Nicholson |
| 2015 | MFCS | Strong Inapproximability of the Shortest Reset Word. | Pawel Gawrychowski, Damian Straszak |
| 2015 | SODA | Wavelet Trees Meet Suffix Trees. | Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya |
| 2015 | SPIRE | Tight Bound for the Number of Distinct Palindromes in a Tree. | Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen |
| 2015 | SPIRE | Computing the Longest Unbordered Substring. | Pawel Gawrychowski, Gregory Kucherov, Benjamin Sach, Tatiana Starikovskaya |
| 2015 | WADS | Universal Reconstruction of a String. | Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2014 | CPM | Computing Minimal and Maximal Suffixes of a Substring Revisited. | Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya |
| 2014 | CPM | Order-Preserving Pattern Matching with k Mismatches. | Pawel Gawrychowski, Przemyslaw Uznanski |
| 2014 | ESA | Weighted Ancestors in Suffix Trees. | Pawel Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson |
| 2014 | ICALP | Improved Submatrix Maximum Queries in Monge Matrices. | Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2014 | ISAAC | Euclidean TSP with Few Inner Points in Linear Space. | Pawel Gawrychowski, Damian Rusak |
| 2014 | LATIN | LZ77-Based Self-indexing with Faster Pattern Matching. | Travis Gagie, Pawel Gawrychowski, Juha Krkkinen, Yakov Nekrich, Simon J. Puglisi |
| 2014 | STACS | Testing Generalised Freeness of Words. | Pawel Gawrychowski, Florin Manea, Dirk Nowotka |
| 2013 | CiE | Discovering Hidden Repetitions in Words. | Pawel Gawrychowski, Florin Manea, Dirk Nowotka |
| 2013 | CPM | Converting SLP to LZ78 in almost Linear Time. | Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga, Masayuki Takeda |
| 2013 | CSR | Alphabetic Minimax Trees in Linear Time. | Pawel Gawrychowski |
| 2013 | ISAAC | Beating $\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching. | Pawel Gawrychowski, Damian Straszak |
| 2013 | STACS | Finding Pseudo-repetitions. | Pawel Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka, Catalin Tiseanu |
| 2013 | SPIRE | Minimal Discriminating Words Problem Revisited. | Pawel Gawrychowski, Gregory Kucherov, Yakov Nekrich, Tatiana Starikovskaya |
| 2012 | CPM | Simple and Efficient LZW-Compressed Multiple Pattern Matching. | Pawel Gawrychowski |
| 2012 | LATA | A Faster Grammar-Based Self-index. | Travis Gagie, Pawel Gawrychowski, Juha Krkkinen, Yakov Nekrich, Simon J. Puglisi |
| 2012 | STACS | Tying up the loose ends in fully LZW-compressed pattern matching. | Pawel Gawrychowski |
| 2012 | SPIRE | Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings. | Pawel Gawrychowski |
| 2011 | ESA | Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic. | Pawel Gawrychowski |
| 2011 | ISAAC | Faster Approximate Pattern Matching in Compressed Repetitive Texts. | Travis Gagie, Pawel Gawrychowski, Simon J. Puglisi |
| 2011 | MFCS | On Minimising Automata with Errors. | Pawel Gawrychowski, Artur Jez, Andreas Maletti |
| 2011 | SODA | Optimal pattern matching in LZW compressed strings. | Pawel Gawrychowski |
| 2010 | CSR | Validating the Knuth-Morris-Pratt Failure Function, Fast and Online. | Pawel Gawrychowski, Artur Jez, Lukasz Jez |
| 2010 | LATA | Grammar-Based Compression in a Streaming Model. | Travis Gagie, Pawel Gawrychowski |
| 2009 | IWOCA | Minimax Trees in Linear Time with Applications. | Pawel Gawrychowski, Travis Gagie |
| 2009 | MFCS | Hyper-minimisation Made Efficient. | Pawel Gawrychowski, Artur Jez |
| 2008 | DLT | Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time. | Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey O. Shallit |
| 2008 | LATA | 2-Synchronizing Words. | Pawel Gawrychowski, Andrzej Kisielewicz |
| 2006 | MFCS | A Combinatorial Approach to Collapsing Words. | Alessandra Cherubini, Pawel Gawrychowski, Andrzej Kisielewicz, Brunetto Piochi |