# Pawel Gawrychowski

According to our database1, Pawel Gawrychowski authored at least 144 papers between 2006 and 2018.

Collaborative distances :

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
The nearest colored node in a tree.
Theor. Comput. Sci., 2018

Speeding up dynamic programming in the line-constrained k-median.
Theory Comput. Syst., 2018

Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets.
Theory Comput. Syst., 2018

Near-Optimal Distance Emulator for Planar Graphs.
CoRR, 2018

Fast entropy-bounded string dictionary look-up with mismatches.
CoRR, 2018

Edit Distance between Unrooted Trees in Cubic Time.
CoRR, 2018

A Faster FPTAS for #Knapsack.
CoRR, 2018

Slowing Down Top Trees for Better Worst-Case Bounds.
CoRR, 2018

Better Tradeoffs for Exact Distance Oracles in Planar Graphs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Optimal Dynamic Strings.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Compression for the Planar Graph Metric.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Faster FPTAS for #Knapsack.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Faster Construction of Greedy Consensus Trees.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Improved Bounds for Shortest Paths in Dense Distance Graphs.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Edit Distance between Unrooted Trees in Cubic Time.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Edit Distance with Block Operations.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Near-Optimal Distance Emulator for Planar Graphs.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Slowing Down Top Trees for Better Worst-Case Compression.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

2017
Longest Gapped Repeats and Palindromes.
Discrete Mathematics & Theoretical Computer Science, 2017

Better Tradeoffs for Exact Distance Oracles in Planar Graphs.
CoRR, 2017

Distinct Squares in Circular Words.
CoRR, 2017

Optimal trade-offs for pattern matching with k mismatches.
CoRR, 2017

Existential length universality.
CoRR, 2017

Optimal Query Time for Encoding Range Majority.
CoRR, 2017

A Faster Construction of Phylogenetic Consensus Trees.
CoRR, 2017

Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
CoRR, 2017

Dispersion on Trees.
CoRR, 2017

Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) time.
CoRR, 2017

A family of approximation algorithms for the maximum duo-preservation string mapping problem.
CoRR, 2017

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).
CoRR, 2017

Near-Optimal Compression for the Planar Graph Metric.
CoRR, 2017

Optimal Query Time for Encoding Range Majority.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Distinct Squares in Circular Words.
Proceedings of the String Processing and Information Retrieval, 2017

Sparse Suffix Tree Construction in Optimal Time and Space.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Optimal Distance Labeling Schemes for Trees.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Dispersion on Trees.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem.
Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016
Order-preserving pattern matching with k mismatches.
Theor. Comput. Sci., 2016

Longest common extensions in trees.
Theor. Comput. Sci., 2016

Computing minimal and maximal suffixes of a substring.
Theor. Comput. Sci., 2016

A note on distance labeling in planar graphs.
CoRR, 2016

Randomized algorithms for finding a majority element.
CoRR, 2016

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
CoRR, 2016

Faster Longest Common Extension Queries in Strings over General Alphabets.
CoRR, 2016

Sparse Suffix Tree Construction in Optimal Time and Space.
CoRR, 2016

Improved Bounds for Shortest Paths in Dense Distance Graphs.
CoRR, 2016

Optimal Distance Labeling Schemes for Trees.
CoRR, 2016

Sublinear-Space Distance Labeling Using Hubs.
Proceedings of the Distributed Computing - 30th International Symposium, 2016

Randomized Algorithms for Finding a Majority Element.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Efficiently Finding All Maximal alpha-gapped Repeats.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Bookmarks in Grammar-Compressed Strings.
Proceedings of the String Processing and Information Retrieval, 2016

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Speeding up Dynamic Programming in the Line-Constrained k-median.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

LZ77 Factorisation of Trees.
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

The Nearest Colored Node in a Tree.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Faster Longest Common Extension Queries in Strings over General Alphabets.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015
Approximate pattern matching in LZ77-compressed texts.
J. Discrete Algorithms, 2015

Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search.
CoRR, 2015

Even Simpler Distance Labeling for (Sparse) Graphs.
CoRR, 2015

Optimal Dynamic Strings.
CoRR, 2015

Efficiently Finding All Maximal $α$-gapped Repeats.
CoRR, 2015

Testing k-binomial equivalence.
CoRR, 2015

Longest Gapped Repeats and Palindromes.
CoRR, 2015

Approximating LZ77 via Small-Space Multiple-Pattern Matching.
CoRR, 2015

Limit Behavior of the Multi-agent Rotor-Router System.
Proceedings of the Distributed Computing - 29th International Symposium, 2015

Universal Reconstruction of a String.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Computing the Longest Unbordered Substring.
Proceedings of the String Processing and Information Retrieval, 2015

Tight Bound for the Number of Distinct Palindromes in a Tree.
Proceedings of the String Processing and Information Retrieval, 2015

Wavelet Trees Meet Suffix Trees.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Strong Inapproximability of the Shortest Reset Word.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Optimal Encodings for Range Top- k k , Selection, and Min-Max.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Longest α-Gapped Repeat and Palindrome.
Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

Approximating LZ77 via Small-Space Multiple-Pattern Matching.
Proceedings of the Algorithms - ESA 2015, 2015

Queries on LZ-Bounded Encodings.
Proceedings of the 2015 Data Compression Conference, 2015

Encodings of Range Maximum-Sum Segment Queries and Applications.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Longest Common Extensions in Trees.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Alphabet-Dependent String Searching with Wexponential Search Trees.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014
Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.
Theory Comput. Syst., 2014

Simple and efficient LZW-compressed multiple pattern matching.
J. Discrete Algorithms, 2014

Encodings of Range Maximum-Sum Segment Queries and Applications.
CoRR, 2014

Tight tradeoffs for approximating palindromes in streams.
CoRR, 2014

Strong inapproximability of the shortest reset word.
CoRR, 2014

Euclidean TSP with few inner points in linear space.
CoRR, 2014

Optimal Encodings for Range Min-Max and Top-k.
CoRR, 2014

Weighted ancestors in suffix trees.
CoRR, 2014

Lock-in Problem for Parallel Rotor-router Walks.
CoRR, 2014

Queries on LZ-Bounded Encodings.
CoRR, 2014

Wavelet Trees Meet Suffix Trees.
CoRR, 2014

Testing Generalised Freeness of Words.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

LZ77-Based Self-indexing with Faster Pattern Matching.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Euclidean TSP with Few Inner Points in Linear Space.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Improved Submatrix Maximum Queries in Monge Matrices.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Weighted Ancestors in Suffix Trees.
Proceedings of the Algorithms - ESA 2014, 2014

Order-Preserving Pattern Matching with k Mismatches.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

Computing Minimal and Maximal Suffixes of a Substring Revisited.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013
Optimal Pattern Matching in LZW Compressed Strings.
ACM Trans. Algorithms, 2013

Minimax trees in linear time with applications.
Eur. J. Comb., 2013

Heaviest Induced Ancestors and Longest Common Substrings
CoRR, 2013

Alphabet-Dependent String Searching with Wexponential Search Trees
CoRR, 2013

Order-preserving pattern matching with k mismatches.
CoRR, 2013

Beating O(nm) in approximate LZW-compressed pattern matching.
CoRR, 2013

Substring Suffix Selection.
CoRR, 2013

Finding Pseudo-repetitions.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Minimal Discriminating Words Problem Revisited.
Proceedings of the String Processing and Information Retrieval, 2013

Beating $\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Alphabetic Minimax Trees in Linear Time.
Proceedings of the Computer Science - Theory and Applications, 2013

Converting SLP to LZ78 in almost Linear Time.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Discovering Hidden Repetitions in Words.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

Heaviest Induced Ancestors and Longest Common Substrings.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

2012
(Really) Tight bounds for dispatching binary methods
CoRR, 2012

Linear-Space Substring Range Counting over Polylogarithmic Alphabets
CoRR, 2012

Tying up the loose ends in fully LZW-compressed pattern matching.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings.
Proceedings of the String Processing and Information Retrieval, 2012

A Faster Grammar-Based Self-index.
Proceedings of the Language and Automata Theory and Applications, 2012

Simple and Efficient LZW-Compressed Multiple Pattern Matching.
Proceedings of the Combinatorial Pattern Matching - 23rd Annual Symposium, 2012

2011
Tying up the loose ends in fully LZW-compressed pattern matching
CoRR, 2011

A Faster LZ77-Based Index
CoRR, 2011

Faster Approximate Pattern Matching in Compressed Repetitive Texts
CoRR, 2011

Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
CoRR, 2011

On minimising automata with errors
CoRR, 2011

Chrobak Normal Form Revisited, with Applications.
Proceedings of the Implementation and Application of Automata, 2011

Optimal pattern matching in LZW compressed strings.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

On Minimising Automata with Errors.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Faster Approximate Pattern Matching in Compressed Repetitive Texts.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic.
Proceedings of the Algorithms - ESA 2011, 2011

2010
On the problem of freeness of multiplicative matrix semigroups.
Theor. Comput. Sci., 2010

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks.
J. Discrete Algorithms, 2010

Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
Int. J. Found. Comput. Sci., 2010

Grammar-Based Compression in a Streaming Model.
Proceedings of the Language and Automata Theory and Applications, 2010

Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.
Proceedings of the Computer Science, 2010

2009
Optimal, online validation of the pi and pi' failure functions
CoRR, 2009

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Minimax Trees in Linear Time with Applications.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Minimax Trees in Linear Time with Applications.
Proceedings of the Search Methodologies, 05.07. - 10.07.2009, 2009

2008
Minimax Trees in Linear Time
CoRR, 2008

2-Synchronizing Words.
Proceedings of the Language and Automata Theory and Applications, 2008

Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time.
Proceedings of the Developments in Language Theory, 12th International Conference, 2008

2006
A Combinatorial Approach to Collapsing Words.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006