Pawel Gawrychowski

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 207

Top Venues

Publications

Pawel Gawrychowski, Wojciech Janczewski
Optimal Distance Labeling for Permutation Graphs. CoRR (2024)
Bartlomiej Dudek, Pawel Gawrychowski
Online Context-Free Recognition in OMv Time. CPM (2024)
Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner
. DCC (2024)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
Sorting Signed Permutations by Reversals in Nearly-Linear Time. SOSA (2024)
Pawel Gawrychowski, Mateusz Wasylkiewicz
Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity. CoRR (2024)
Duncan Adamson, Pawel Gawrychowski, Florin Manea
Enumerating m-Length Walks in Directed Graphs with Constant Delay. CoRR (2024)
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Simon R. Tarnow
Faster Sliding Window String Indexing in Streams. CPM (2024)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Samah Ghazawi
Optimal Bounds for Distinct Quartics. CoRR (2024)
Bartlomiej Dudek, Pawel Gawrychowski
Slowing down top trees for better worst-case compression. Theor. Comput. Sci. 1015 (2024)
Duncan Adamson, Pawel Gawrychowski, Florin Manea
Enumerating m-Length Walks in Directed Graphs with Constant Delay. LATIN (1) (2024)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Samah Ghazawi
Optimal Bounds for Distinct Quartics. ICALP (2024)
Jonas Ellert, Pawel Gawrychowski, Garance Gourdel
Optimal Square Detection Over General Alphabets. SODA (2023)
Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau
Order-Preserving Squares in Strings. CPM (2023)
Panagiotis Charalampopoulos, Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski
Optimal Near-Linear Space Heaviest Induced Ancestors. CPM (2023)
Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner
Compressed Indexing for Consecutive Occurrences. CoRR (2023)
Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski, Solon P. Pissis
Substring Complexity in Sublinear Space. ISAAC (2023)
Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau
Order-Preserving Squares in Strings. CoRR (2023)
Jonas Ellert, Pawel Gawrychowski, Garance Gourdel
Optimal Square Detection Over General Alphabets. CoRR (2023)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
Sorting Signed Permutations by Reversals in Nearly-Linear Time. CoRR (2023)
Pawel Gawrychowski, Maria Kosche, Florin Manea
On the Number of Factors in the LZ-End Factorization. SPIRE (2023)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen
Almost Optimal Exact Distance Oracles for Planar Graphs. J. ACM 70 (2) (2023)
Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner
Compressed Indexing for Consecutive Occurrences. CPM (2023)
Pawel Gawrychowski, Przemyslaw Uznanski
Better Distance Labeling for Unweighted Planar Graphs. Algorithmica 85 (6) (2023)
Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen
Tight Bound for the Number of Distinct Palindromes in a Tree. Electron. J. Comb. 30 (2) (2023)
Panagiotis Charalampopoulos, Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski
Optimal Heaviest Induced Ancestors. CoRR (2023)
Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann
The Theory of Universal Graphs for Infinite Duration Games. Log. Methods Comput. Sci. 18 (3) (2022)
Pawel Gawrychowski, Karol Pokorski
Sublinear Dynamic Interval Scheduling (on one or multiple machines). CoRR (2022)
Simon Apers, Pawel Gawrychowski, Troy Lee
Finding the KT Partition of a Weighted Graph in Near-Linear Time. APPROX/RANDOM (2022)
Moses Ganardi, Pawel Gawrychowski
Pattern Matching on Grammar-Compressed Strings in Linear Time. SODA (2022)
Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone
Elastic-Degenerate String Matching via Fast Matrix Multiplication. SIAM J. Comput. 51 (3) (2022)
Pawel Gawrychowski, Mateusz Rzepecki
Faster Exponential Algorithm for Permutation Pattern Matching. SOSA (2022)
Pawel Gawrychowski, Florin Manea, Stefan Siemer
Matching Patterns with Variables Under Edit Distance. CoRR (2022)
Pawel Gawrychowski, Tatiana Starikovskaya
Streaming Dictionary Matching with Mismatches. Algorithmica 84 (4) (2022)
Pawel Gawrychowski, Florin Manea, Stefan Siemer
Matching Patterns with Variables Under Edit Distance. SPIRE (2022)
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut query algorithms with star contraction. CoRR (2022)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann
On the Hardness of Computing the Edit Distance of Shallow Trees. SPIRE (2022)
Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Fault-tolerant distance labeling for planar graphs. Theor. Comput. Sci. 918 (2022)
Pawel Gawrychowski, Florin Manea, Radoslaw Serafin
Fast and Longest Rollercoasters. Algorithmica 84 (4) (2022)
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut Query Algorithms with Star Contraction. FOCS (2022)
Bartlomiej Dudek, Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya
Streaming Regular Expression Membership and Pattern Matching. SODA (2022)
Pawel Gawrychowski, Wojciech Janczewski
Simpler Adjacency Labeling for Planar Graphs with B-Trees. SOSA (2022)
Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski
The Dynamic k-Mismatch Problem. CPM (2022)
Pawel Gawrychowski, Karol Pokorski
Sublinear Dynamic Interval Scheduling (On One or Multiple Machines). ICALP (2022)
Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski
Shorter Labels for Routing in Trees. SODA (2021)
Djamal Belazzougui, Manuel Cáceres, Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Gonzalo Navarro, Alberto Ordóñez Pereira, Simon J. Puglisi, Yasuo Tabei
Block trees. J. Comput. Syst. Sci. 117 (2021)
Simon Apers, Pawel Gawrychowski, Troy Lee
Finding the KT partition of a weighted graph in near-linear time. CoRR (2021)
Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau
Lower Bounds for the Number of Repetitions in 2D Strings. SPIRE (2021)
Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Fault-Tolerant Distance Labeling for Planar Graphs. CoRR (2021)
Moses Ganardi, Pawel Gawrychowski
Pattern Matching on Grammar-Compressed Strings in Linear Time. CoRR (2021)
Pawel Gawrychowski, Maria Kosche, Tore Koß, Florin Manea, Stefan Siemer
Efficiently Testing Simon's Congruence. STACS (2021)
Pawel Gawrychowski, Shay Mozes, Oren Weimann
A Note on a Recent Algorithm for Minimum Cut. SOSA (2021)
Pawel Gawrychowski, Shay Mozes, Oren Weimann
-Cycle. SODA (2021)
Pawel Gawrychowski, Florin Manea, Stefan Siemer
Matching Patterns with Variables under Hamming Distance. CoRR (2021)
Pawel Gawrychowski, Florin Manea, Stefan Siemer
Matching Patterns with Variables Under Hamming Distance. MFCS (2021)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann
An Almost Optimal Edit Distance Oracle. CoRR (2021)
Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann
The Theory of Universal Graphs for Infinite Duration Games. CoRR (2021)
Pawel Gawrychowski, Wojciech Janczewski
Conditional Lower Bounds for Variants of Dynamic LIS. CoRR (2021)
Golnaz Badkobeh, Pawel Gawrychowski, Juha Kärkkäinen, Simon J. Puglisi, Bella Zhukova
Tight upper and lower bounds on suffix tree breadth. Theor. Comput. Sci. 854 (2021)
Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski
Incomplete Directed Perfect Phylogeny in Linear Time. WADS (2021)
Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Fault-Tolerant Distance Labeling for Planar Graphs. SIROCCO (2021)
Pawel Gawrychowski, Mateusz Rzepecki
Faster Exponential Algorithm for Permutation Pattern Matching. CoRR (2021)
Pawel Gawrychowski, Przemyslaw Uznanski
Better Distance Labeling for Unweighted Planar Graphs. WADS (2021)
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann
Top Tree Compression of Tries. Algorithmica 83 (12) (2021)
Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann
) Time. SIAM J. Comput. 50 (2) (2021)
Pawel Gawrychowski, Wojciech Janczewski
Fully dynamic approximation of LIS in polylogarithmic time. STOC (2021)
Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski
The Dynamic k-Mismatch Problem. CoRR (2021)
Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau
Lower Bounds for the Number of Repetitions in 2D Strings. CoRR (2021)
Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski
Strictly In-Place Algorithms for Permuting and Inverting Permutations. WADS (2021)
Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski
Strictly In-Place Algorithms for Permuting and Inverting Permutations. CoRR (2021)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann
An Almost Optimal Edit Distance Oracle. ICALP (2021)
Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau
On Indeterminate Strings Matching. CPM (2020)
Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski, Solon P. Pissis
Substring Complexity in Sublinear Space. CoRR (2020)
Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski
Shorter Labels for Routing in Trees. CoRR (2020)
Pawel Gawrychowski, Shay Mozes, Oren Weimann
A Note on a Recent Algorithm for Minimum Cut. CoRR (2020)
Bartlomiej Dudek, Pawel Gawrychowski
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. ISAAC (2020)
Maciej Duleba, Pawel Gawrychowski, Wojciech Janczewski
Efficient Labeling for Reachability in Digraphs. CoRR (2020)
Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann
Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. MFCS (2020)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
All non-trivial variants of 3-LDT are equivalent. CoRR (2020)
Pawel Gawrychowski, Seungbum Jo, Shay Mozes, Oren Weimann
Compressed range minimum queries. Theor. Comput. Sci. 812 (2020)
Anadi Agrawal, Pawel Gawrychowski
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem. CoRR (2020)
Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can). ACM Trans. Algorithms 16 (4) (2020)
Pawel Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey O. Shallit, Marek Szykula
Existential Length Universality. STACS (2020)
Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski
On Two Measures of Distance between Fully-Labelled Trees. CoRR (2020)
Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski
On Two Measures of Distance Between Fully-Labelled Trees. CPM (2020)
Maciej Duleba, Pawel Gawrychowski, Wojciech Janczewski
Efficient Labeling for Reachability in Directed Acyclic Graphs. ISAAC (2020)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
All non-trivial variants of 3-LDT are equivalent. STOC (2020)
Pawel Gawrychowski, Wojciech Janczewski
Fully Dynamic Approximation of LIS in Polylogarithmic Time. CoRR (2020)
Pawel Gawrychowski, Shay Mozes, Oren Weimann
Minimum Cut in O(m log² n) Time. ICALP (2020)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
Generalised Pattern Matching Revisited. STACS (2020)
Pawel Gawrychowski, Maria Kosche, Tore Koss, Florin Manea, Stefan Siemer
Efficiently Testing Simon's Congruence. CoRR (2020)
Bartlomiej Dudek, Pawel Gawrychowski
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. CoRR (2020)
Pawel Gawrychowski, Shay Mozes, Oren Weimann
Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search. ACM Trans. Algorithms 16 (2) (2020)
Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
Universal reconstruction of a string. Theor. Comput. Sci. 812 (2020)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
Generalised Pattern Matching Revisited. CoRR (2020)
Anadi Agrawal, Pawel Gawrychowski
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem. ISAAC (2020)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Karol Pokorski
Dynamic Longest Common Substring in Polylogarithmic Time. ICALP (2020)
Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen
Tight Bound for the Number of Distinct Palindromes in a Tree. CoRR (2020)
Panagiotis Charalampopoulos, Pawel Gawrychowski, Karol Pokorski
Dynamic Longest Common Substring in Polylogarithmic Time. CoRR (2020)
Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski
Incomplete Directed Perfect Phylogeny in Linear Time. CoRR (2020)
Pawel Gawrychowski, Tatiana Starikovskaya
Streaming Dictionary Matching with Mismatches. CPM (2019)

Pawel Gawrychowski.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Pawel Gawrychowski