Dominik Pająk

e-mail: dominik.pajak [at]

My dblp.

My profile on google scholar.

Research interests

Graph exploration with mobile agents, Ad Hoc networks


  1. Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol, with Frederik Mallmann-Trenn, Yannic Maus, ICALP'19
  2. On Simple Back-Off in Complicated Radio Networks, with Seth Gilbert, Nancy Lynch and Calvin Newport, OPODIS'18, Brief Announcement in DISC'18, journal version in Theoretical Computer Science vol. 806
  3. Brief Announcement: Broadcast in radio networks: time vs. energy tradeoffs, with Marek Klonowski, PODC'18
  4. Time and space optimality of rotor-router graph exploration: with Artur Menc and Przemyslaw Uznanski: Information Processing Letters 127
  5. On Location Hiding in Distributed Systems, with Karol Gotfryd and Marek Klonowski, SIROCCO'17
  6. Multiple Random Walks on Paths and Grids, with Andrej Ivaskovic, Adrian Kosowski and Thomas Sauerwald, STACS'17
  7. Approximating the Size of a Radio Network in Beeping Model, with Philipp Brandes, Marcin Kardas, Marek Klonowski and Roger Wattenhofer, SIROCCO'16, journal version in Theoretical Computer Science vol. 810
  8. Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry, with Ralf Klasing and Adrian Kosowski, SIROCCO'16
  9. Linear search by a pair of distinct-speed robots, with Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing and Tomasz Kociumaka, SIROCCO'16, journal version in Algorithmica vol. 81
  10. Fence Patrolling with Two-Speed Robots, with Konstantinos Georgiou, Fraser MacQuarrie, Evangelos Kranakis and Jurek Czyzowicz, ICORES'16
  11. Information Spreading by Mobile Particles on a Line, with Jurek Czyzowicz, Evangelos Kranakis and Eduardo Pacheco: SIROCCO'15
  12. Electing a Leader in Wireless Networks Quickly Despite Jamming, with Marek Klonowski, SPAA'15
  13. Distinguishing Views in Symmetric Networks: A Tight Lower Bound, with Dariusz Dereniowski and Adrian Kosowski, Theoretical Computer Science vol. 582
  14. Evacuating Robots via Unknown Exit in a Disk, with Jurek Czyżowicz, Leszek Gąsieniec, Thomas Gorry, Evangelos Kranakis and Russell Martin, DISC'14
  15. Patrolling by Robots Equipped with Visibility, with Jurek Czyżowicz, Evangelos Kranakis and Najmeh Taleb, SIROCCO'14
  16. Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router, with Adrian Kosowski, ICALP'14, journal version in Journal of Computer an System Science vol. 106
  17. Bounds on the Cover Time of Parallel Rotor Walks, with Dariusz Dereniowski, Adrian Kosowski, and Przemysław Uznański: STACS’14, journal version in Journal of Computer an System Science vol. 82
  18. Collision-Free Network Exploration, with Jurek Czyżowicz, Dariusz Dereniowski, Leszek Gąsieniec, Ralf Klasing and Adrian Kosowski, LATIN’14
  19. Fast Collaborative Graph Exploration, with Dariusz Dereniowski, Yann Disser, Adrian Kosowski and Przemysław Uznański, Best Paper Award at ICALP’13 track C, presentation, journal version in Information and Computation vol. 582
  20. The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks, with Ralf Klasing, Adrian Kosowski and Thomas Sauerwald, PODC’13, presentation, journal version in Distributed Computing vol. 30
  21. Energy-Effective Leader Election Protocols for Networks with Collision Detection, with Marcin Kardas and Marek Klonowski, ICPP’13
  22. k-Selection Protocols from Energetic Complexity Perspective, with Kamil Wolny, Marcin Kardas and Marek Klonowski: APDCM’13, journal version in IJNC vol. 4
  23. Maximum Matching in Multi-Interface Networks, COCOA’12, presentation, with Adrian Kosowski, Alfredo Navarra and Maria Cristina Pinotti, journal version in Theoretical Computer Science vol. 507
  24. On λ-Alert Problem, with Marek Klonowski, IPDPS’12



  • 2011 - 2014 PhD student, Inria Bordeaux Sud-Ouest, (advisors: Ralf Klasing, Adrian Kosowski, title: Algorithms for Deterministic Parallel Graph Exploration)
  • 2006 - 2011 M.Sc. Eng. in Computer Science, Wroclaw University of Technology, (advisor: Marek Klonowski, title: Threshold Alert problem in radio ad hoc network)