David Ilcinkas

About

David Ilcinkas is a prominent theoretical computer scientist whose research sits at the intersection of distributed computing, graph theory, and autonomous mobile agents. His work primarily addresses fundamental questions about how computational agents — whether finite automata or mobile robots — can explore and navigate complex graph structures under severe constraints of limited memory, lack of communication, and asynchronous operation. Among his most influential contributions is his investigation into label-guided graph exploration by finite automata, demonstrating how topological labeling can overcome inherent limitations of memory-restricted agents (91 citations). Equally significant is his pioneering work on "oblivious robots" — agents with no persistent memory — showing that even such severely limited entities can collectively explore trees and rings without direct communication, a counterintuitive and theoretically elegant result that has attracted over 80 citations per paper. His work on digraph exploration with minimal memory (80 citations) and asynchronous rendezvous problems in infinite grids (72 citations) further demonstrates his broad command of algorithmic challenges in distributed environments. With multiple papers exceeding 60 citations and a body of work spanning over a decade, Ilcinkas has made enduring contributions to understanding the fundamental computational power and limitations of autonomous agents, making his research essential reading for students of distributed algorithms and mobile computing.

Research Focus

Key Achievements

Top Papers

1. 1
   Remembering without memory: Tree exploration by asynchronous oblivious robots

   91 citations · 2010
2. 2
   Label-guided graph exploration by a finite automaton

   91 citations · 2008
3. 3
   Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots

   82 citations · 2012
4. 4
   Digraphs Exploration with Little Memory

   80 citations · 2004
5. 5
   Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids

   72 citations · 2010
6. 6
   Tree exploration with advice

   63 citations · 2008
7. 7
   Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots

   54 citations · 2008
8. 8
   How many oblivious robots can explore a line

   40 citations · 2011
9. 9
   Graph Exploration by a Finite Automaton

   26 citations · 2004
10. 10
    Tree Exploration with an Oracle

    24 citations · 2006

Key Collaborators

Contact & Links