My research focuses on algorithms and complexity analysis. Topics:Tools:
- Distributed computing
- Communication protocols
- Mobile computing
- Combinatorial structures
- Randomised algorithms
- Approximation techniques
- Competitive analysis
- Game theory
- Information theory
Conference version: Proc. of the 27th Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 135-144
Conference version: Proc. of the 27th Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 375-384
Conference version: Proc. of the 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2008, pp. 291-305
Conference version: Energy and time efficient broadcasting in known topology radio networks, Proc. of the 21st International Symposium on Distributed Computing, DISC 2007, pp. 253-267
Journal version: Distributed Computing 21 (2008) 117-127 (DISC 2007 special issue)
Conference version: Proc. of the 21st International Symposium on Distributed Computing, DISC 2007, pp. 283-297
Conference version: Proc. of the 21st International Symposium on Distributed Computing, DISC 2007, pp. 328-342
Conference version: Proc. of the 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2007, pp. 124-138
Conference version: Proc. of the 25th ACM Symposium on Principles of Distributed Computing, PODC 2006, pp. 92-101
Conference version: Proc. of the 20th International Symposium on Distributed Computing, DISC 2006, pp. 314-328
Conference version: Proc. of the 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, pp. 253-267
Conference version: Proc. of the 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, pp. 44-58
Journal version: Theoretical Computer Science 399 (2008) 141-156 (SIROCCO 2006 special issue)
Conference version: On many-to-many communication in packet radio networks, Proc. of the 10th International Conference on Principles of Distributed Systems, OPODIS 2006, pp. 260-274
Journal version: Algorithmica, to appear
Journal version: Fundamenta Informaticae 71 (2006) 229-242
Conference version: Proc. of the 9th International Conference on Principles of Distributed Systems, OPODIS 2005, pp. 206-220
Conference version: in Proc. of the 15th International Symposium on Fundamentals of Computation Theory, FCT 2005, pp. 270-280
Conference version: Proc. of the 32nd International Col loquium on Automata, Languages and Programming, ICALP 2005, pp. 347-359
Conference version: Proc. of the 24th ACM Symposium on Principles of Distributed Computing, PODC 2005, pp. 158-166
Conference version: Proc. of the 37th ACM Symposium on Theory of Computing, STOC 2005, pp. 733-739
Conference version: Proc. of the 25th International Conference on Distributed Computing Systems, ICDCS 2005, pp. 49-58
Conference version: Proc. of the 2nd International Conference on Wireless on Demand Network Systems and Service, WoNS 2005, pp. 119-124
Journal version: Journal of Parallel and Distributed Computing (special issue on Algorithms for Wireless and Ad-Hoc Networks) 66:4 (2006) 578-585
Conference version: Energy efficient connectivity in ad hoc networks from user's and designer's perspective, in Proc. of the 40th IEEE Internationl Conference on Communications, ICC 2005
Journal version: Mobile Computing and Communications Review 9:1 (2005) 15 - 26
Conference version: Proc. of the 6th Latin American Symposium on Theoretical Informatics, LATIN 2004, pp. 141-151
Journal version: Networks 48:3 (2006) 166-177
Conference version: Writing-All deterministically and optimally using a non-trivial number of asynchronous processors, in Proc. of the 16th ACM Symposium on Paral lel Algorithms and Architectures, SPAA 2004, pp. 311-320
Journal version: ACM Transactions on Algorithms 4 (2008)
Conference version: Searching for a black hole in tree networks, in Proc. of the 8th International Conference on Principles of Distributed Systems, OPODIS 2004, pp. 67-80
Journal version: Combinatorics, Probability and Computing 16 (2007) 595-619
Conference version: The Wake-Up problem in multi-hop radio networks, in Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 992-1000
Journal version: SIAM Journal on Computing 36:5 (2007) 1453-1471
Preliminary conference version: Centralized deterministic broadcasting in undirected multi-hop radio networks, in Proc. of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, LNCS 3122, pp. 171-182
Journal version: Distributed Computing 19:3 (2007) 185-195
Preliminary conference version: Polynomial deterministic rendezvous in arbitrary graphs, in Proc. of the 15th International Symposium on Algorithms and Computation, ISAAC 2004, LNCS 3341, pp. 644-656 (only with A. Pelc)
Journal version: Algorithmica 46 (2006) 69-96 (ISAAC 2004 special issue)
Conference version: Proc. of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2004, pp. 266-274
Conference version: Proc. of the 36th ACM Symposium on Theory of Computing, STOC 2004, pp. 321-330
Conference version: Proc. of the International Conference on Dependable Systems and Networks, DSN 2004, pp. 315-324
Conference version: Proc. of the 22nd ACM Symposium on Principles of Distributed Computing, PODC 2003, pp. 265-274
Journal version: Information and Computation 203:2 (2005) 181-210
Conference version: Proc. of the 22nd ACM Symposium on Principles of Distributed Computing, PODC 2003, pp. 73-82
Journal version: Distributed Computing 18:1 (2005) 43-57 (PODC 2003 special issue)
Conference version: Proc. of the 17th International Symposium on Distributed Computing, DISC 2003, pp. 224-238
Journal version: Theoretical Computer Science 347:1-2 (2005) 130-166
Conference version: Proc. of the 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003,Springer, pp. 109-120
Journal version: SIAM Journal on Discrete Mathematics 18:2 (2004) 332-346
Conference version: Time of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism, in Proc. of the 10th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2003, pp. 195-210
Journal version: Theoretical Computer Science 333:3 (2005) 355-371 (SIROCCO 2003 special issue)
Conference version: Proc. of the 7th Interantional Conference On Principles of Distributed Systems, OPODIS 2003, pp. 210-222
Conference version: Deterministic broadcasting time in radio networks of unknown topology, in Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 63-72
Journal version: SIAM Journal on Computing 33:4 (2004) 870-891
Conference version: Gossiping to reach consensus, in Proc. of the 14th ACM Symposium on Parallel Algorithms and Architectures, SPAA 2002, pp. 220-229
Journal version: Journal of Computer and System Sciences 72:8 (2006) 1262-1281
Conference version: Finding spanning forests by broadcasting, in Proc. of the 9th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2002, pp. 41-56
Journal version: Theory of Computing Systems 36 (2003) 711-733 (SIROCCO 2002 special issue)
Conference version: Proc. of the 16th International Symposium on Distributed Computing, DISC 2002, pp. 295-310
Conference version: Proc. of the 13th ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, pp. 271-280
Conference version: The Do-All problem in broadcast networks, in Proc. of the 20th ACM Symposium on Principles of Distributed Computing, PODC 2001, pp. 117-126
Journal version: Distributed Computing 18:6 (2006) 435-451
Conference version: Randomization helps to perform tasks on processors prone to failures, in Proc. of the 13th International Symposium on Distributed Computing, DISC 1999,LNCS 1693, pp. 284-296
Journal version: Random Structures and Algorithms 24 (2004) 11-41