Przemysław (Przemek) Uznański

I am a Postdoctoral Researcher at Department of Computer Science, ETH Zürich, Switzerland.

e-mail: przemyslaw.uznanski [at] inf.ethz.ch

Research

Scientific Interests:

  • Randomness in Computation (Random Walks, Derandomization of random processes)
  • Restricted Models of Computation (streaming, low memory)
  • Self Organization (biological agents, token circulation, load balancing)
  • Distributed Computing and Locality
  • Algebraic Methods in Algorithms

Conferences:

Programme committee:

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

Teaching

Ongoing:

Past:

Students

  • Karim Labib [2017-2018] (master thesis, co-supervised with Daniel Graf, slides)
  • Stefan Tiegel [2017] (ETH summer internship, co-supervised with Daniel Graf)
  • Jan Studený [2018] (ETH summer internship)

Education and Previous Employment

  • 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)

List of publications

please also refer to: google scholar, dblp

Pre-prints:

Faster Algorithms for All-Pairs Bounded Min-Cuts with A. Abboud, L. Georgiadis, D. Graf, G. F. Italiano, R. Krauthgamer, N. Parotsidis and O. Trabelsi.

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

Conference Publications:

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

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.)

Hamming distance completeness and sparse matrix multiplication with D. Graf and K. Labib. (Slides, 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.)

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:

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.)