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

In the programme committee of SIROCCO 2016 and IWOCA 2016.

I gave invited talk at MICRO MAC workshop: slides (use Acrobat reader, animated!)


Teaching

Ongoing:
Past:


Education and Previous Employment

  • 2015.01-2015.11 Postdoc at Department of Computer ScienceAalto University, Finland
  • 2013-2014 Postdoc at LIFCNRS 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 scholardblp


Pre-prints:

  1. D. Dereniowski, A. Kosowski, P. Uznański and M. Zou
    "
    Approximation Strategies for Generalized Binary Search in Weighted Trees"
    (arXivhal)
  2. 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"
    (arXiv, slides)
  3. A. Kosowski and P. Uznański
    "Ergodic Effects in Token Circulation" 
    (
    arXiv)
  4. L. Georgiadis, D. Graf, G. F. Italiano, N. Parotsidis and P. Uznański
    "All-Pairs 2-reachability in Õ(nω) Time" 
    (
    arXiv, slides)
  5. P. Gawrychowski and P. Uznański
    "A note on distance labeling in planar graphs" 
    (arXiv)
  6. P. Uznański
    "

    All Permutations Supersequence is coNP-complete

    " 
    (arXiv)
  7. A. Menc, D. Pająk and P. Uznański
    "Time and space optimality of rotor-router graph exploration" 
    (arXiv)


Conference Publications:

  1. P. Gawrychowski, A. Kosowski and P. Uznański
    "Sublinear-Space Distance Labeling using Hubs"
    (DISC 2016arXivslides)
    "Brief announcement: 

    Sublinear-Space Distance Labeling using Hubs

    "

    (PODC2016slides)
  2. P. Gawrychowski, O. Merkurev, A. M. Shur and P. Uznański:
    "Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams"
    (arxivCPM 2016slides)
    P. Gawrychowski and P. Uznański
    "Tight tradeoffs for approximating palindromes in streams"
    (arXiv)
  3. P. Gawrychowski, J. Suomela and P. Uznański
    "

    Randomized algorithms for finding a majority element"


    (arXivSWAT 2016slides)
  4. M. Mihalák, P. Uznański and P. Yordanov
    "Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences"
    (arXivANALCO 2016slides)
  5. J. Chalopin, S. Das, P. Gawrychowski, A. Kosowski, A. Labourel and P. Uznański 
    "Limit Behavior of the Multi-agent Rotor-Router System"
    (arXivDISC 2015, animated slides
  6. P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn and P. Uznański 
    "

    Improved Analysis of Deterministic Load-Balancing Schemes

    "

    (arXivPODC 2015)
  7. 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"
    (arXivICALP-A 2015)
  8. S. Das, D. Dereniowski, A. Kosowski and P. Uznański 
    "Rendezvous of Distance-aware Mobile Agents in Unknown Graphs"
    (arXivSIROCCO 2014slides)
  9. P. Gawrychowski and P. Uznański
    "Order-preserving pattern matching with k mismatches"
    (arXivCPM 2014)
  10. L. Eyraud-Dubois and P. Uznański
    "Point-to-point and congestion bandwidth estimation: experimental evaluation on PlanetLab"
    (halIPDPSW 2014 (HCW))
  11. A. Kosowski, D. Dereniowski, D. Pająk and P. Uznański
    "Bounds on the Cover Time of Parallel Rotor Walks"
    (halSTACS 2014slides)
  12. A. Kosowski and P. Uznański
    "Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice"
    (halEUROPAR 2013slides)
  13. D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk and P. Uznański
    "Fast Collaborative Graph Exploration"
    (halICALP-C 2013, abstract: ALGOTEL 2013slides)
    Best paper award at ICALP-C 2013
  14. L. Eyraud-Dubois and P. Uznański
    "Bedibe: Datasets and Software Tools for Distributed Bandwidth Prediction"
    (ALGOTEL 2012)
  15. 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"
    (halICPADS 2011slides)


Journal Publications:
  1. A. Kosowski, D. Dereniowski, D. Pająk and P. Uznański
    "Bounds on the Cover Time of Parallel Rotor Walks"
  2. P. Gawrychowski and P. Uznański
    "Order-preserving pattern matching with k mismatches"
  3. D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk and P. Uznański
    "Fast Collaborative Graph Exploration"
  4. 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"