Skip to main content

Research Repository

Advanced Search

Browse


Sorting and Hypergraph Orientation under Uncertainty with Predictions (2023)
Conference Proceeding
Erlebach, T., de Lima, M., Megow, N., & Schlöter, J. (2023). Sorting and Hypergraph Orientation under Uncertainty with Predictions. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (5577-5585). https://doi.org/10.24963/ijcai.2023/619

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to min... Read More about Sorting and Hypergraph Orientation under Uncertainty with Predictions.

Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots (2023)
Conference Proceeding
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2023). Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (47-57). https://doi.org/10.1109/IPDPS54959.2023.00015

Over the years, much research involving mobile computational entities has been performed. From modeling actual microscopic (and smaller) robots, to modeling software processes on a network, many important problems have been studied in this context. G... Read More about Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots.

Physical-layer Jammer Detection in Multi-hop IoT Networks (2023)
Journal Article
Abdollahi, M., Malekinasab, K., Tu, W., & Bag-Mohammadi, M. (in press). Physical-layer Jammer Detection in Multi-hop IoT Networks. IEEE Internet of Things Journal, https://doi.org/10.1109/JIOT.2023.3291997

The presence of a jammer in an IoT network severely degrades all communication efforts between adjacent wireless devices. The situation is getting worse due to retransmission attempts made by affected devices. Therefore, jammers must be detected or l... Read More about Physical-layer Jammer Detection in Multi-hop IoT Networks.

Optimal (degree+1)-Coloring in Congested Clique (2023)
Conference Proceeding
Coy, S., Czumaj, A., Davies, P., & Mishra, G. (2023). Optimal (degree+1)-Coloring in Congested Clique. In K. Etessami, U. Feige, & G. Puppis (Eds.), 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) (99:1-99:20). https://doi.org/10.4230/LIPIcs.ICALP.2023.46

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u) + 1 colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list co... Read More about Optimal (degree+1)-Coloring in Congested Clique.

Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization (2023)
Conference Proceeding
Davies, P. (2023). Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization. . https://doi.org/10.1145/3583668.3594595

In the study of radio networks, the tasks of broadcasting (propagating a message throughout the network) and leader election (having the network agree on a node to designate ‘leader’) are two of the most fundamental global problems, and have a long h... Read More about Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization.

Distributed MIS in O(log log n) Awake Complexity (2023)
Conference Proceeding
Dufoulon, F., Moses Jr., W. K., Pandurangan, G., & Nolin, A. (2023). Distributed MIS in O(log log n) Awake Complexity. . https://doi.org/10.1145/3583668.3594574

Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have O(log n) round complexity on genera... Read More about Distributed MIS in O(log log n) Awake Complexity.

GDPR compliance verification through a user-centric blockchain approach in multi-cloud environment (2023)
Journal Article
Ahmad, H., & Aujla, G. S. (2023). GDPR compliance verification through a user-centric blockchain approach in multi-cloud environment. Computers and Electrical Engineering, 109, https://doi.org/10.1016/j.compeleceng.2023.108747

With cloud-hosted web applications becoming ubiquitous, the security risks presented for user personal data that is migrated to the cloud are at an all-time high. When using a cloud-hosted web application, users only ever interact with web interfaces... Read More about GDPR compliance verification through a user-centric blockchain approach in multi-cloud environment.

On the Capacity Region of a Quantum Switch with Entanglement Purification (2023)
Presentation / Conference
Panigrahy, N. K., Vasantam, T., Towsley, D., & Tassiulas, L. (2023, May). On the Capacity Region of a Quantum Switch with Entanglement Purification. Paper presented at INFOCOM 2023: IEEE International Conference on Computer Communications, New York

Quantum switches are envisioned to be an integral component of future entanglement distribution networks. They can provide high quality entanglement distribution service to end-users by performing quantum operations such as entanglement swapping and... Read More about On the Capacity Region of a Quantum Switch with Entanglement Purification.

Termination of amnesiac flooding (2023)
Journal Article
Hussak, W., & Trehan, A. (2023). Termination of amnesiac flooding. Distributed Computing, 36(2), 193-207. https://doi.org/10.1007/s00446-023-00448-y

We consider a stateless ‘amnesiac’ variant of the stateful distributed network flooding algorithm, expanding on our conference papers [PODC’19, STACS’20]. Flooding begins with a set of source ‘initial’ nodes I seeking to broadcast a message M in roun... Read More about Termination of amnesiac flooding.

An accurate RSS/AoA-based localization method for internet of underwater things (2023)
Journal Article
Pourkabirian, A., Kooshki, F., Anisi, M. H., & Jindal, A. (2023). An accurate RSS/AoA-based localization method for internet of underwater things. Ad Hoc Networks, 145, Article 103177. https://doi.org/10.1016/j.adhoc.2023.103177

Localization is an important issue for Internet of Underwater Things (IoUT) since the performance of a large number of underwater applications highly relies on the position information of underwater sensors. In this paper, we propose a hybrid localiz... Read More about An accurate RSS/AoA-based localization method for internet of underwater things.

Parameterized temporal exploration problems (2023)
Journal Article
Erlebach, T., & Spooner, J. T. (2023). Parameterized temporal exploration problems. Journal of Computer and System Sciences, 135, 73-88. https://doi.org/10.1016/j.jcss.2023.01.003

In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph G admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices.... Read More about Parameterized temporal exploration problems.

Payment scheduling in the Interval Debt Model (2023)
Conference Proceeding
Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. . https://doi.org/10.1007/978-3-031-23101-8_18

The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introd... Read More about Payment scheduling in the Interval Debt Model.

Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring (2023)
Conference Proceeding
Davies, P. (2023). Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (4273-4295). https://doi.org/10.1137/1.9781611977554.ch163

The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have n ‘bad events’, each of which occurs wit... Read More about Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring.

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty (2022)
Conference Proceeding
Erlebach, T., de Lima, M. S., Megow, N., Schlöter, J., Chechik, S., Navarro, G., …Herman, G. (2022). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In 30th Annual European Symposium on Algorithms (ESA 2022) (12:1-12:16). https://doi.org/10.4230/lipics.esa.2022.12

We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundam... Read More about Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.