I am a Researcher/Software Engineer at NavAlgo,

AND

an Assistant Professor at Institute of Computer Science, University of Wrocław, Poland.

przemek [at] navalgo.com

puznanski [at] cs.uni.wroc.pl

Scientific Interests:

I am interested in constructing efficient algorithms for processing big data sets. More specifically, I am interested in exploiting inherent parallelism appearing in many problems for constructing efficient algorithms. This applies not only to parallel computation, but to classical centralised computation, and other models like streaming processing, or massively parallel computation. In my work I use not only algorithmical techniques, but also algebra and linear algebra extensively, as well as probabilistic analysis and high-dimensional geometry. I am also interested in proving lower-bounds and showing limitations to techniques.

Students

Ongoing:

  • Aleksander Łukasiewicz [2020-] PhD

Past students:

  • Aleksander Łukasiewicz [2020] (master thesis)

  • Jan Studený [2018] (ETH summer internship)

  • Karim Labib [2018] (master thesis, co-supervised with Daniel Graf, slides)

  • Stefan Tiegel [2017] (ETH summer internship, co-supervised with Daniel Graf)

Conferences

Programme committees:

Keynotes and invited talks:

  • Invited talk at MICRO MAC 2016 workshop (slides, animated, use Acrobat reader)

  • Invited talk at CiE 2020 special session on Combinatorial Pattern Matching

Funding

  • [2020-2023] Head of a project Polish National Science Centre OPUS 2019/33/B/ST6/00298 ''Algebraic techniques of parallelising algorithms''.

  • [2019-2022] Co-investigator in a project Polish National Science Centre OPUS 2018/31/B/ST6/00820 „Graph modelling of searching processes”.

Education and Employment

  • 2020.01-ongoing Researcher/Software Engineer at NavAlgo

  • 2019.02-ongoing Assistant Professor at Institute of Computer Science, University of Wrocław, Poland

  • 2019.01-2019.12 Senior Software Developer at Testify AS

  • 2015.12-2019.01 Postdoc at Department of Computer Science, ETH Zürich, Switzerland

  • 2015.01-2015.11 Postdoc at Department of Computer Science, Aalto University, Finland

  • 2013-2014 Postdoc at LIF, CNRS and Aix-Marseille University, France

  • 2010-2013, Ph.D. student, Inria Bordeaux Sud-Ouest, France (advisors: O. Beaumont, N. Bonichon, L. Eyraud-Dubois): "Large scale platform: Instantiable models and algorithmic design of communication schemes" (hal version, slides)

  • 2006-2010, M.Sc. in Computer Science, University of Wrocław, (advisor: G. Stachowiak), title: ”Problem ”Whac-A-Mole” na zbiorach dekrementacyjnych” (in polish)

Teaching

Ongoing:

  • (UWr) Fall 2020, TA: Machine Learning

  • (UWr) Fall 2020, TA: Wstęp do Programowania w języku Python

Past:

List of publications

Pre-prints:

The Dynamic k-Mismatch Problem with R. Clifford, P. Gawrychowski, T. Kociumaka and D. P. Martin.

Robust Comparison in Population Protocols with D. Alistarh and M. Töpfer

Distributed Colour Reduction Revisited with J. Kohonen, J. H. Korhonen, C. Purcell and J. Suomela.

Conference Publications:

All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier with F. Grandoni, G. F. Italiano, A. Łukasiewicz and N. Parotsidis. (Accepted to SODA 2021.)

Improved Circular k-Mismatch Sketches with S. Golan, T. Kociumaka, T. Kopelowitz and E. Porat. (Presented at APPROX 2020, youtube.)

Lp Pattern Matching in a Stream with T. Starikovskaya and M. Svagerka. (Presented at APPROX 2020, slides, youtube.)

Recent advances in text-to-pattern distance algorithms. (Presented at CiE 2020, slides.)

RLE edit distance in near optimal time with R. Clifford, P. Gawrychowski, T. Kociumaka and D. P. Martin. (Presented at MFCS 2019, slides.)

Faster Algorithms for All-Pairs Bounded Min-Cuts with A. Abboud, L. Georgiadis, G. F. Italiano, R. Krauthgamer, N. Parotsidis, O. Trabelsi and D. Wolleb-Graf. (Presented at ICALP 2019, slides, HALG 2019 poster.)

Hamming distance completeness with K. Labib and D. Wolleb-Graf. (Slides, Brief announcement at ICALP 2018, slides, presented at CPM 2019, best paper award, slides.)

A Framework for Searching in Graphs in the Presence of Errors with D. Dereniowski, S. Tiegel and D. Wolleb-Graf. (Presented at SOSA 2019, slides, HALG 2019 poster.)

Population Protocols Are Fast with A. Kosowski. (Brief announcement at PODC 2018, slides, HALG 2018 poster.)

Energy Constrained Depth First Search with S. Das and D. Dereniowski. (Brief announcement at ICALP 2018, slides.)

Ergodic Effects in Token Circulation with A. Kosowski. (Presented at SODA 2018, animated slides. Presented at HALG 2018, animated slides, poster.)

Robust Detection in Leak-Prone Population Protocols with D. Alistarh, B. Dudek, A. Kosowski and D. Soloveichik. (Presented at DNA 2017, arXiv, slides.)

LCL problems on grids with S. Brandt, J. Hirvonen, J. H. Korhonen, T. Lempiäinen, P. R. J. Östergård, C. Purcell, J. Rybicki and J. Suomela. (Presented at PODC 2017, arXiv, slides.)

All-Pairs 2-reachability in O(nω log n) Time with L. Georgiadis, D. Graf, G. F. Italiano and N. Parotsidis. (Presented at ICALP 2017, slides.)

Approximation Strategies for Generalized Binary Search in Weighted Trees with D. Dereniowski, A. Kosowski and M. Zou. (Presented at ICALP 2017, slides.)

Sublinear-Space Distance Labeling using Hubs with P. Gawrychowski and A. Kosowski. (Presented at DISC 2016, arXiv, slides. Brief announcement at PODC2016, slides.)

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams with P. Gawrychowski, O. Merkurev and A. M. Shur. (Presented at CPM 2016, slides.)

Randomized algorithms for finding a majority element with P. Gawrychowski and J. Suomela. (Presented at SWAT 2016, slides.)

Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences with M. Mihalák and P. Yordanov. (Presented at ANALCO 2016, slides.)

Limit Behavior of the Multi-agent Rotor-Router System with J. Chalopin, S. Das, P. Gawrychowski, A. Kosowski and A. Labourel. (Presented at DISC 2015, arXiv, animated slides.)

Improved Analysis of Deterministic Load-Balancing Schemes with P. Berenbrink, R. Klasing, A. Kosowski and F. Mallmann-Trenn. (Presented at PODC 2015, arXiv.)

On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols with J. Czyżowicz, L. Gąsieniec, A. Kosowski, E. Kranakis and P. Spirakis. (Presented at ICALP 2015, arXiv.)

Rendezvous of Distance-aware Mobile Agents in Unknown Graphs with S. Das, D. Dereniowski and A. Kosowski. (Presented at SIROCCO 2014, arXiv, slides.)

Order-preserving pattern matching with k mismatches with P. Gawrychowski. (Presented at CPM 2014, arXiv, youtube.)

Bounds on the Cover Time of Parallel Rotor Walks with A. Kosowski, D. Dereniowski and D. Pająk. (Presented at STACS 2014, slides.)

Fast Collaborative Graph Exploration with D. Dereniowski, Y. Disser, A. Kosowski and D. Pająk. (Presented at ICALP 2013, best paper award, hal, slides, abstract: ALGOTEL 2013.)

Bedibe: Datasets and Software Tools for Distributed Bandwidth Prediction with L. Eyraud-Dubois. (Presented at ALGOTEL 2012.)

Broadcasting on Large Scale Heterogeneous Platforms with connectivity artifacts under the Bounded Multi-Port Model with O. Beaumont, N. Bonichon and L. Eyraud-Dubois. (Presented at ICPADS 2011, hal, slides.)

Journal Publications:

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams with P. Gawrychowski, O. Merkurev and A. M. Shur. (Published in Algorithmica, Volume 81 Issue 9.)

Improved Analysis of Deterministic Load-Balancing Schemes with P. Berenbrink, R. Klasing, A. Kosowski and F. Mallmann-Trenn. (Published in ACM Transactions on Algorithms, Volume 15 Issue 1.)

Time and space optimality of rotor-router graph exploration with A. Menc and D. Pająk. (Published in Information Processing Letters, Volume 127.)

Bounds on the Cover Time of Parallel Rotor Walks with A. Kosowski, D. Dereniowski and D. Pająk. (Published in Journal of Computer and System Science, Volume 82.)

Order-preserving pattern matching with k mismatches with P. Gawrychowski. (Published in Theoretical Computer Science, Volume 638 - CPM 2014 Special Issue.)

Fast Collaborative Graph Exploration with D. Dereniowski, Y. Disser, A. Kosowski and D. Pająk. (Published in Information and Computation, Volume 243 - ICALP 2013 Special Issue.)

Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model with O. Beaumont, N. Bonichon, L. Eyraud-Dubois and S. K. Agrawal. (Published in IEEE Transactions on Parallel and Distributed Systems, Volume 25.)