# 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:

- [ongoing] SPIRE 2018
- [ongoing] ALGOCLOUD 2018
- ICDCS 2018
- SIROCCO 2016
- IWOCA 2016.

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

## Teaching

### Ongoing:

- (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

### Past:

- (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) Autumn 2016, TA: Algorithmic Game Theory
- (ETH) Autumn 2016, TA: Algorithms Lab
- (ETH) Autumn 2016, TA: Discrete Math
- (ETH) Spring 2016, TA: Seminar on Algorithms for Database Systems
- (Aalto) Autumn 2015, TA: ICS-E5020 Distributed algorithms
- (Aalto) Autumn 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

## 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:

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)

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)

### Conference Publications:

P. Gawrychowski and __P. Uznański__

**"Towards Unified Approximate Pattern Matching for Hamming and L _{1} Distance"**

(ICALP 2018, arXiv1, arXiv2, 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)

M. Mihalák, __P. Uznański__ and P. Yordanov

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

(arXiv, ANALCO 2016, slides)

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"**

S. Das, D. Dereniowski, A. Kosowski and __P. Uznański__

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

(arXiv, SIROCCO 2014, slides)

L. Eyraud-Dubois and __P. Uznański__

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

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"**

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"**

A. Kosowski, D. Dereniowski, D. Pająk and __P. Uznański__

**"Bounds on the Cover Time of Parallel Rotor Walks"**

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)