Przemysław (Przemek) Uznański

Postdoctoral Researcher

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

also see: google scholar, dblp

Pre-prints:

J. Studený and P. Uznański

"Approximating Approximate Pattern Matching"

(arxiv)

A. Abboud, L. Georgiadis, D. Graf, G. F. Italiano, R. Krauthgamer, N. Parotsidis, O. Trabelsi and P. Uznański

"Faster Algorithms for All-Pairs Bounded Min-Cuts"

(arxiv)

A. Kosowski and P. Uznański

"Population Protocols Are Fast"

(arXiv, Brief Announcement: PODC 2018 slides, HALG 2018 poster)

L. Gąsieniec, G. Stachowiak and P. Uznański

"Almost logarithmic-time space optimal leader election in population protocols"

(arXiv)

D. Graf, K. Labib and P. Uznański

"Hamming distance completeness and sparse matrix multiplication"

(arXiv, slides, Brief Announcement: ICALP 2018, slides)

S. Das, D. Dereniowski and P. Uznański

"Energy Constrained Depth First Search"

(arXiv, Brief Announcement: ICALP 2018, slides)

J. Kohonen, J. H. Korhonen, C. Purcell, J. Suomela and P. Uznański

"Distributed Colour Reduction Revisited"

(arXiv)

P. Gawrychowski and P. Uznański

"A note on distance labeling in planar graphs"

(arXiv)

P. Uznański

"All Permutations Supersequence is coNP-complete"

(arXiv)

Conference Publications:

D. Dereniowski, D. Graf, S. Tiegel and P. Uznański

"A Framework for Searching in Graphs in the Presence of Errors"

(arxiv, to appear: SOSA 2019, slides)

P. Gawrychowski and P. Uznański

"Towards Unified Approximate Pattern Matching for Hamming and L1 Distance"

(ICALP 2018, arXiv1, arXiv2, slides)

A. Kosowski and P. Uznański

"Ergodic Effects in Token Circulation"

(SODA 2018, arXiv, slides - animated, use Acrobat reader, HALG 2018 slides - animated, use Acrobat reader, poster)

D. Alistarh, B. Dudek, A. Kosowski, D. Soloveichik and P. Uznański

"Robust Detection in Leak-Prone Population Protocols"

(DNA23, arXiv, slides)

S. Brandt, J. Hirvonen, J. H. Korhonen, T. Lempiäinen, P. R. J. Östergård, C. Purcell, J. Rybicki, J. Suomela and P. Uznański

"LCL problems on grids"

(PODC 2017, arXiv, slides)

L. Georgiadis, D. Graf, G. F. Italiano, N. Parotsidis and P. Uznański

"All-Pairs 2-reachability in O(nω log n) Time"

(ICALP 2017, arXiv, slides)

D. Dereniowski, A. Kosowski, P. Uznański and M. Zou

"Approximation Strategies for Generalized Binary Search in Weighted Trees"

(ICALP 2017, arXiv, hal, slides)

P. Gawrychowski, A. Kosowski and P. Uznański

"Sublinear-Space Distance Labeling using Hubs"

(DISC 2016, arXiv, slides, Brief Announcement: PODC2016, slides)

P. Gawrychowski, O. Merkurev, A. M. Shur and P. Uznański:

"Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams"

(arxiv, CPM 2016, slides)

P. Gawrychowski and P. Uznański

"Tight tradeoffs for approximating palindromes in streams"

(arXiv)

P. Gawrychowski, J. Suomela and P. Uznański

"Randomized algorithms for finding a majority element"

(arXiv, SWAT 2016, slides)

M. Mihalák, P. Uznański and P. Yordanov

"Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences"

(arXiv, ANALCO 2016, slides)

J. Chalopin, S. Das, P. Gawrychowski, A. Kosowski, A. Labourel and P. Uznański

"Limit Behavior of the Multi-agent Rotor-Router System"

(arXiv, DISC 2015, animated slides)

P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn and P. Uznański

"Improved Analysis of Deterministic Load-Balancing Schemes"

(arXiv, PODC 2015)

J. Czyżowicz, L. Gąsieniec, A. Kosowski, E. Kranakis, P. Spirakis and P. Uznański

"On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols"

(arXiv, ICALP-A 2015)

S. Das, D. Dereniowski, A. Kosowski and P. Uznański

"Rendezvous of Distance-aware Mobile Agents in Unknown Graphs"

(arXiv, SIROCCO 2014, slides)

P. Gawrychowski and P. Uznański

"Order-preserving pattern matching with k mismatches"

(arXiv, CPM 2014)

L. Eyraud-Dubois and P. Uznański

"Point-to-point and congestion bandwidth estimation: experimental evaluation on PlanetLab"

(hal, IPDPSW 2014 (HCW))

A. Kosowski, D. Dereniowski, D. Pająk and P. Uznański

"Bounds on the Cover Time of Parallel Rotor Walks"

(STACS 2014, hal, slides)

A. Kosowski and P. Uznański

"Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice"

(EUROPAR 2013, hal, slides)

D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk and P. Uznański

"Fast Collaborative Graph Exploration"

(hal, ICALP-C 2013, abstract: ALGOTEL 2013, slides)

Best paper award at ICALP-C 2013

L. Eyraud-Dubois and P. Uznański

"Bedibe: Datasets and Software Tools for Distributed Bandwidth Prediction"

(ALGOTEL 2012)

O. Beaumont, N. Bonichon, L. Eyraud-Dubois and P. Uznański

"Broadcasting on Large Scale Heterogeneous Platforms with connectivity artifacts under the Bounded Multi-Port Model"

(ICPADS 2011, hal, slides)

Journal Publications:

A. Menc, D. Pająk and P. Uznański

"Time and space optimality of rotor-router graph exploration"

(arXiv, Information Processing Letters)

A. Kosowski, D. Dereniowski, D. Pająk and P. Uznański

"Bounds on the Cover Time of Parallel Rotor Walks"

(Journal of Computer and System Science, Volume 82)

P. Gawrychowski and P. Uznański

"Order-preserving pattern matching with k mismatches"

(Theoretical Computer Science, Volume 638 - CPM 2014 Special Issue)

D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk and P. Uznański

"Fast Collaborative Graph Exploration"

(Information and Computation, Volume 243 - ICALP 2013 Special Issue)

O. Beaumont, N. Bonichon, L. Eyraud-Dubois, P. Uznański and S. K. Agrawal

"Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model"

(IEEE Transactions on Parallel and Distributed Systems, Volume 25)