General research interest: Design and analysis of discrete algorithms for combinatorial problems, with a special interest in string algorithms (pattern matching) and string combinatorics (regularities, data structures), text compression (dictionary methods, block sorting, simple grammars), parallel algorithms and architectures (PRAM, hypercube and meshes), and distributed computing (mobile computing, radio networks, communication tasks including broadcasting and gossiping). Current involvement in projects include:

Network design and communication: We study efficient communication primitives in radio networks with known and unknown topology. The main emphasis is on broadcasting (one-to-all communication), gossiping (all-to-all communication), waking up and synchronisation protocols, routing, multicast, and others. Our recent papers on the topic include:

-- Leszek Gasieniec, Erez Kantor, Dariusz R. Kowalski, David Peleg, Chang Su, Energy and Time Efficient Broadcasting in Known Topology Radio Networks,
21st International Symposium on Distributed Computing, DISC 2007, LNCS 4731, pp. 253-267.
-- Yuval Emek, Leszek Gasieniec, Erez Kantor, Andrzej Pelc, David Peleg, Chang Su, Broadcasting in udg radio networks with unknown topology,
26th annual ACM symposium on principles of distributed computing, PODC 2007, pp. 195-204.
-- Leszek Gasieniec, Aris Pagourtzis, Igor Potapov, Tomasz Radzik, Deterministic Communication in Radio Networks with Large Labels,
Algorithmica, Volume 47(1), pp 97-117 (2007).
-- Leszek Gasieniec, Chang Su, Prudence W.H. Wong, Qin Xin, Routing of Single-source and Multiple-source Queries in Static Sensor Networks,
Journal of Discrete Algorithms, 5(1), pp. 1-11 (2007).
-- Leszek Gasieniec, David Peleg, Qin Xin, Faster communication in known topology radio networks,
Distributed Computing, 19(4), pp. 289-300 (2007).
-- Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski, The Wake-Up Problem in MultiHop Radio Networks,
SIAM Journal on Computing, Volume 36(5), pp 1453-1471 (2007).
-- Leszek Gasieniec, Igor Potapov, Qin Xin, Time efficient centralized gossiping in radio networks,
Theoretical Computer Science, Volume 383(1), pp. 45-58 (2007).
-- Robert Elsaesser, Leszek Gasieniec, Radio communication in random graphs,
Journal of Computer and System Sciences, 72(3), pp. 490-506 (2006).
-- Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin Deterministic M2M Multicast in Radio Networks,
Theoretical Computer Science 362(1-3), pp. 196-206 (2006).

Efficient exploration and rendezvous methods: We work on efficient exploration of unknown environment modeled by graphs or Euclidean space as well as fast and reliable rendezvous methods. Depending on the context the task is performed either by a single robot (agent) or by a team of collaborating robots. We consider models with various levels of communication, synchronisation and adaptivity. Selected papers on the topic include:

-- Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, Xiaohui (Cloud) Zhang, Fast Periodic Graph Exploration with Constant Memory.,
Journal of Computer and System Sciences Vol 74(5), August 2008, pp. 808-822.
-- Leszek Gasieniec, Andrzej Pelc, Tomasz Radzik, Xiaohui (Cloud) Zhang, Tree exploration with logarithmic memory,
18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 585-594 (SODA'07).
-- Jurek Czyzowicz, Leszek Gasieniec, Andrzej Pelc, Gathering few fat mobile robots in the plane,
10th International Conference on Principles of Distributed Systems, LNCS 4305, pp. 350-364, (OPODIS'2006).
-- Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski, Andrzej Pelc, Collective tree exploration
Networks 48(3), pp. 166-177 (2006)
-- Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Xiaohui (Cloud) Zhang, Optimal Memory Rendezvous of Anonymous Mobile Agents in a Unidirectional Ring,
LNCS 3831 pp. 282-292 (SOFSEM'06).

Combinatorial algorithms and structures in Bioinformatics: We study various combinatorial and algorithmic problems that occur in the context of obtaining, storage and analysis of biological data. This includes modeling of biological processes as well as provision of efficient combinatorial algorithms and data structures supporting, e.g., filtering, classification, mining of DNA amd RNA sequences. A list of recent papers on the topic include:

-- Leszek Gasieniec, Ying (Cindy) Li, Meng Zhang, Faster Algorithm for the Set Variant of the String Barcoding Problem,
19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008, LNCS 5029, pp. 82-94.
-- Amihood Amir, Leszek Gasieniec, B. Riva Shalom, Improved approximate common interval,
Information Processing Letters, Volume 103(4), pp. 142-149 (2007).
-- Leszek Gasieniec, Ying (Cindy) Li, Paul Sant, Prudence W.H. Wong, Ramdomised probe selection algorihtm for microarray design,
Journal of Theoretical Biology, 248(3), pp. 512-521, (2007).
-- Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro, Optimal Two-Stage Algorithms for Group Testing Problems,
SIAM Journal on Computing, 34(5), pp. 1253-1270, (2005).
-- Peter Clote, Leszek Gasieniec, Roman M. Kolpakov, Evangelos Kranakis, Danny Krizanc, On realizing shapes in the theory of RNA neutral networks,
Journal of Theoretical Biology, 236(2), pp. 216-227, (2005).

More comprehensive list of papers can be found here.

Recently held grants

Current PhD Students

-- Andrew Collins (from October'09)
-- Ojiaku, Jude-Thaddeus N.K (from November'10)

Former PhD Students

-- Frantisek Galcik (visitor Sep'08-Dec'08)
-- Ying (Cindy) Li (graduated in 2008)
-- Qin Xin (graduated in 2004)
-- Su Chang (graduated in 2007)
-- Xiaohui (Cloud) Zhang (graduated in 2007)

Research opportunities

Will be advertised here. Please note that I DO NOT respond to requests for summer internships, PhD studentships, etc, which are not advertised on this page.

Other

List of co-authors

L.A.Gasieniec@liverpool.ac.uk