Homepage
Pawel Gawrychowski
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 321
66123 Saarbrücken
Germany
Email:
Get my email address via email
I'm interested in pretty much everything with an algorithmic flavour, but all my publications so far are in the following areas:
- data structures
- text algorithms
- formal languages
- Paweł Gawrychowski: Pattern matching in compressed text, my PhD thesis (already defended, yay!), (pdf) (slides from my defense)
- Paweł Gawrychowski, (Really) Tight bounds for dispatching binary methods, submitted
- Paweł Gawrychowski, Simple and efficient LZW-compressed multiple pattern matching, accepted to CPM 2012
- Travis Gagie, Paweł Gawrychowski, Juha Karkkainen, Yakov Nekrich, and Simon Puglisi, A faster grammar-based self-index, LATA 2012
- Paweł Gawrychowski: Tying up the loose ends in fully LZW-compressed pattern matching, STACS 2012 (arxiv)
- Travis Gagie, Paweł Gawrychowski, Simon Puglisi, Faster approximate pattern matching in compressed repetetive texts, ISAAC 2011 (arxiv), invited to the special issue of Algorithmica
- 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)
- Paweł Gawrychowski: Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic, ESA 2011 (arxiv) (presentation), invited to the special issue of Algorithmica
- Paweł Gawrychowski: Optimal pattern matching in LZW compressed strings, SODA 2011 (conference version) (presentation), invited to the special issue of ACM Transactions on Algorithms (preliminary journal version)
- Paweł Gawrychowski: Alphabetic minimax trees in linear time, submitted (preliminary version)
- 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)
- 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)
- Paweł Gawrychowski, Travis Gagie: Minimax trees in linear time with applications, IWOCA 2009 (arXiv)
- 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 IJFCS (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 (arXiv) (journal version)
- Paweł Gawrychowski, Andrzej Kisielewicz: 2-synchronizing words, LATA 2008 (link to PDF) (presentation)
- Paweł Gawrychowski, Andrzej Kisielewicz: Recognizing 2-synchronizing words, AutoMathA 2007
- Alessandra Cherubini, Paweł Gawrychowski, Andrzej Kisielewicz, Brunetto Piochi: A combinatorial approach to collapsing words, MFCS 2006 (link to PDF) (presentation)
- October 2007 - September 2011:
Ph. D. student in Computer Science at the University of Wrocław
- October 2002 - July 2007:
Studies in Computer Science at the University of Wrocław
Hobbies
- competitive programming, see here if you are interested!
