I am a Researcher/Software Engineer at Pathway,
AND
an Assistant Professor at Institute of Computer Science, University of Wrocław, Poland.
My detailed CV,
additional info: google scholar, dblp, ORCID, SCOPUS, ResearchGate, LinkedIn
przemek [at] pathway.com
puznanski [at] cs.uni.wroc.pl
I used to do competetive programming too: profile.
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:
ICDCS 2023 (Distributed Algorithms and Theory track)
ICDCS 2021 (Distributed Algorithms and Theory track)
ICDCS 2018 (Distributed Algorithms and Theory track)
Organizing committees:
Dagstuhl-Seminar 23071 From Big Data Theory to Big Data Practice
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 Data Structures and Optimization Expert at Pathway
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
(UWr) Spring 2022, Lecturer: Algorithms for Big Data
(UWr) Spring 2022, TA: Sztuczna Inteligencja
(UWr) Spring 2021, TA: Sztuczna Inteligencja
(UWr) Spring 2021, TA: Seminarium algorytmika w środowisku sieciowym
(UWr) Fall 2020, TA: Machine Learning
(UWr) Fall 2020, TA: Wstęp do Programowania w języku Python
(UWr) Spring 2020, Coordinator: Algebra
(UWr) Spring 2019, TA: Kurs C++
(UWr) Fall 2019, Lecturer: Algorithms for Big Data
(UWr) Fall 2019, TA: Machine Learning
(UWr) Spring 2019, TA: Algebra
(UWr) Spring 2019, TA: Rachunek Prawdopodobieństwa i Statystyka
(UWr) Spring 2019, TA: Kurs C++
(ETH) Spring 2018, Lecturer: Advanced Data Structures
(ETH) Spring 2018, TA: Seminar on Algorithms for Database Systems
(ETH) Spring 2018, TA: Seminar on Advanced Algorithms and Data Structures
(ETH) Spring 2017, Lecturer: Advanced Data Structures
(ETH) Spring 2017, TA: Seminar on Algorithms for Database Systems
Finnish IOI training camp: tutorials on hashing and number theory
(ETH) Fall 2016, TA: Algorithmic Game Theory
(ETH) Fall 2016, TA: Algorithms Lab
(ETH) Fall 2016, TA: Discrete Math
(ETH) Spring 2016, TA: Seminar on Algorithms for Database Systems
(Aalto) Fall 2015, TA: ICS-E5020 Distributed algorithms
(Aalto) Fall 2015, TA: CSE-E5001 Algorithmic problem solving and programming contests
(Aalto) Spring 2015, TA: T-106.6200 Special Course in Software Engineering: Introduction to Algorithmic Problem Solving and Programming Contests
List of publications
Conference Publications:
Cardinality estimation using Gumbel distribution with A. Łukasiewicz. (Presented at ESA S 2022.)
The Dynamic k-Mismatch Problem with R. Clifford, P. Gawrychowski, T. Kociumaka and D. P. Martin. (Presented at CPM 2022, best paper award.)
A time and space optimal stable population protocol solving exact majority with D. Doty, M. Eftekhari, L. Gąsieniec, E. Severson and G. Stachowiak. (Presented at FOCS 2021.)
An Efficient Noisy Binary Search in Graphs via Median Approximation with D. Dereniowski and A. Łukasiewicz. (Presented at IWOCA 2021.)
Comparison Dynamics in Population Protocols with D. Alistarh and M. Töpfer. (Presented at PODC 2021.)
Better distance labeling for unweighted planar graphs with P. Gawrychowski. (Presented at WADS 2021, best paper award.)
All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier with F. Grandoni, G. F. Italiano, A. Łukasiewicz and N. Parotsidis. (Presented at 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.)
Approximating Text-to-Pattern Distance via Dimensionality Reduction. (Presented at CPM 2020, slides, youtube.)
RLE edit distance in near optimal time with R. Clifford, P. Gawrychowski, T. Kociumaka and D. P. Martin. (Presented at MFCS 2019, slides.)
Hardness of exact distance queries in graphs through hub labeling with A. Kosowski and L. Viennot. (Presented at PODC 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.)
Almost logarithmic-time space optimal leader election in population protocols with L. Gąsieniec and G. Stachowiak. (Presented at SPAA 2019, slides.)
Approximating Approximate Pattern Matching with J. Studený. (Presented at CPM 2019, slides.)
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.)
Towards Unified Approximate Pattern Matching for Hamming and L1 Distance with P. Gawrychowski. (Presented at ICALP 2018, slides.)
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.)
Point-to-point and congestion bandwidth estimation: experimental evaluation on PlanetLab with L. Eyraud-Dubois. (Presented at IPDPSW 2014 (HCW), hal.)
Bounds on the Cover Time of Parallel Rotor Walks with A. Kosowski, D. Dereniowski and D. Pająk. (Presented at STACS 2014, slides.)
Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice with A. Kosowski. (Presented at EUROPAR 2013, hal, 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:
Better distance labeling for unweighted planar graphs with P. Gawrychowski. (Published in Algorithmica, Volume 85 Issue 6.)
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. (Published in Journal of Computer and System Science, Volume 130.)
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.)
Other:
From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071) with M. Farach-Colton, F. Kuhn and R. Rubinfeld.
Pre-prints:
Pathway: a fast and flexible unified stream data processing framework for analytical and Machine Learning applications with M. Bartoszkiewicz, J. Chorowski, A. Kosowski, J. Kowalski, S. Kulik, M. Lewandowski, K. Nowicki, K. Piechowiak, O. Ruas and Z. Stamirowska.
Noisy searching: simple, fast and correct with D. Dereniowski and A. Łukasiewicz.
Distributed Colour Reduction Revisited with J. Kohonen, J. H. Korhonen, C. Purcell and J. Suomela.