Nýjar víddir í reikniritum fyrir þráðlaus net - verkefni lokið

Fréttatilkynning verkefnisstjóra

31.5.2023

The project “Post-modern models of wireless algorithms” that received an IRF grant from 2017 through 2019, has now been completed. The results from the project have been reported in 17 journal papers as well as 26 publications in competitive conferences, three of which received best paper awards. A major impact of the project has been improved understanding of basic fundamental properties of wireless networking,
particularly in settings with significant unreliability or environmental changes. Additionally, significant improvements have been obtained in distributed algorithms for graph coloring, perhaps the most fundamental problem in distributed computing. The research was performed primarily at ICE-TCS, Icelandic Center of Excellence in Theoretical Computer Science, at Reykjavik University, in collaboration with researchers in Germany, United States, and Switzerland.

Publications
All of the publications are available open-access, either on arXiv, on ResearchGate/Semantic Scholar, or on the authors' private websites (and often on all of these). We would like to draw special attention to journal paper 6 (incorporating award-winning conference paper 3) and journal paper 5 (from conference papers 8 and 10).

Journal Publications on SINR Model
1. Magnús M. Halldórsson, Yuexuan Wang and Dongxiao Yu. Leveraging Multiple Channels in Ad Hoc Networks. Distributed Computing, 32(2):159–172, April 2019. DOI:10.1007/s00446-018-0329-3.
2. Magnús M. Halldórsson, Stephan Holzer, Evangelia Anna Markatou, Nancy Lynch. Leader Election in SINR Model with Arbitrary Power Control. Theoretical Computer Science 811:21–28, 2 April 2020.
3. Magnús M. Halldórsson, Tigran Tonoyan. Limitations of Current Wireless Scheduling Algorithms.Theoretical Computer Science 840:154–165, 6 November 2020.
4. Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, and Hoon Oh. Radio Ag-gregation Scheduling. Theoretical Computer Science 840:143-153, 6 Nov 2020.
5. Magnús M. Halldórsson and Tigran Tonoyan. Sparse Backbone and Optimal Distributed SINR Algo-rithms. ACM Transactions on Algorithms (TALG) 17(2), May 2021.
6. Magnús M. Halldórsson and Tigran Tonoyan. Effective Wireless Scheduling via Hypergraph Sketches. SIAM Journal of Computing, 50(2):718–759, 2021.
7. Magnús M. Halldórsson and Tigran Tonoyan. Computing inductive vertex orderings. Information Processing Letters 172, 2021.
8. Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan. Spanning Trees With Edge Conflicts and Wireless Connectivity. Algorithmica 83(11), 2021.

Journal Publications on Distributed Computing and Related Aspect
9. Magnús M. Halldórsson, Christian Konrad. Distributed Large Independent Sets in a Single Round. Distributed Computing 31:69–82, 2018.
10. Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir, Dror Rawitz. Distributed Backup Placement in Networks. Distributed Computing 31:83, 2018. DOI:10.1007/s00446-017-0299-x.
11. Magnús M. Halldórsson, Sven Köhler, Dror Rawitz. Distributed Approximation of k-Service Assignment. Distributed Computing 32(1):27–40, February 2019. DOI:10.1007/s00446-017-0321-3.
12. Magnús M. Halldórsson, Christian Konrad. Distributed Algorithms for Coloring Interval Graphs with Applications to Multicoloring Trees. Theoretical Computer Science 811:29–41, 2 April 2020.
13. Ravi Boppana, Magnús M. Halldórsson, Dror Rawitz. Simple and Local Independent Set Approx-imation. Theoretical Computer Science 846:27-37, 18 December 2020. Special issue of SIROCCO 2018. https://authors.elsevier.com/c/1b˜fQ15DaI4Nmf

Other Refereed Journal Publications
14. K.M.J. De Bontridder, B.V. Halldorsson, M.M. Halldórsson, C.A.J. Hurkens, J.K. Lenstra, R. Ravi,and L. Stougie. Local improvement algorithms for a path packing problem: A performance analysis based on linear programming. Operations Research Letters 49(1):62–68, January 2021.
15. Magnús M. Halldórsson, Murilo Santos de Lima. Query-Competitive Sorting with Uncertainty. Theoretical Computer Science, 867:50–67, 6 May 2021.
16. Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima, Tigran Tonoyan. Query Mini-mization under Stochastic Uncertainty. Theoretical Computer Science, 895:75–95, 4 December 2021.
17. Magnús M. Halldórsson, Toshimasa Ishii, Kazuhisa Makino and Kenjiro Takazawa. Posimodular Function Optimization. Algorithmica, 84(4):1107–1131, April 2022. https://rdcu.be/cFZNa

Refereed Conference Publications on SINR Model
1. Magnús M. Halldórsson, Tigran Tonoyan, Yuexuan Wang, Dongxiao Yu. Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier Sense. In Proc. 31st International Parallel and Distributed Processing Symposium (IPDPS), Florida, May 2017.
2. Magnús M. Halldórsson, Stephan Holzer, Evangelia Anna Markatou. Leader Election in SINR Model with Arbitrary Power Control. In Proc. 24th Int'l Colloq. Structural Information and Communication Complexity (SIROCCO), Porquerolles, France, June 2017. Received Best Paper Award.
3. Eyjólfur I. Ásgeirsson, Magnús M. Halldórsson, Tigran Tonoyan. Universal Framework for Wire-less Scheduling Problems. In Proc. 44th International Conference on Automata, Languages, and Programming (ICALP), Warzaw, Poland, July 2017. Received Best Paper Award. Invited for presentation at Highlights of Algorithms, June 2018.
4. Magnús M. Halldórsson, Tigran Tonoyan. Wireless Link Capacity under Shadowing and Fading. In Proc. Eighteenth International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHoc), Chennai, July 2017.
5. Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. An Efficient Communica-tion Abstraction for Dense Wireless Networks. In Proc. 31st International Symposium on DIStributed Computing (DISC), Vienna, Austria, October 2017.
6. Magnús M. Halldórsson, Tigran Tonoyan. Wireless Aggregation at Nearly Constant Rate. In Proc. 38th IEEE International Conference on Distributed Computing Systems (ICDCS), Vienna, July 2018.
7. Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan. Spanning Trees With Edge Conflicts and Wireless Connectivity. In Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, July 2018.
8. Magnús M. Halldórsson, Tigran Tonoyan. Leveraging Indirect Signaling for Topology Inference and Fast Broadcast. In Proc. 37th ACM Symposium on Principles of Distributed Computing (PODC),London, July 2018.
9. Magnús M. Halldórsson, Tigran Tonoyan. Link Scheduling under Correlated Shadowing. In Proc.WiOpt, Avignon, June 2019.
10. Magnús M. Halldórsson, Tigran Tonoyan. Plain SINR is Enough! In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, July 2019.

Relevant Conference Publications on Distributed Computing
11. Magnús M. Halldórsson, Christian Konrad. Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees. In Proc. 24th Int'l Colloq. Structural Information and Communication Complexity (SIROCCO), Porquerolles, France, June 2017.
12. Ravi Boppana, Magnús M. Halldórsson, Dror Rawitz. Simple and Local Independent Set Approxi-mation. In Proc. SIROCCO, Jerusalem, June 2018.
13. Michael Dinitz, Magnús M. Halldórsson, Taisuke Izumi, Calvin Newport. Distributed Minimum Degree Spanning Trees. In Proc. PODC, Toronto, July 2019.
14. Michael Dinitz, Magnús M. Halldórsson, Calvin Newport, Alex Weaver. The Capacity of Smartphone Peer-To-Peer Networks. In Proc. DISC, Budapest, October 2019. LIPIcs, Vol. 146. https://doi.org/10.4230/LIPIcs.DISC.2019.14
15. Pierre Fraigniaud, Magnús M. Halldórsson, Alexandre Nolin. Testing distance-k colorings in CONGEST. In SIROCCO, July 2020.
16. Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus. Distance-2 coloring in CONGEST. In PODC, August 2020.
17. Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Alexandre Nolin. Coloring fast without all the connections. In DISC, October 2020.
18. Magnús M. Halldórsson, Alexandre Nolin. Superfast Coloring in CONGEST via Efficient Color Sampling. In SIROCCO, June 2021. Springer LNCS. Received Best Paper Award.
19. Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan. Efficient Randomized Dis-tributed Coloring in CONGEST. In STOC, June 2021.
20. Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, Tigran Tonoyan. Nearly Optimal Distributed Degree+1-Coloring. In STOC, June 2022.
21. Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan. Overcoming Congestion in Distributed Coloring. In PODC, July 2022.

Other Conference Publications
22. Magnús M. Halldórsson, Toshimasa Ishii, Kazuhisa Makino and Kenjiro Takazawa. Posimodular Function Optimization. In Proc. Algorithms and Data Structures Symposium (WADS), St. John's, Canada, July 2017.
23. Magnús M. Halldórsson, Murilo Santos de Lima. Query-Competitive Sorting with Uncertainty. In Proc. MFCS, Aachen, August 2019. LIPIcs.
24. Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima, Tigran Tonoyan. Query Mini- mization under Stochastic Uncertainty. In Proc. LATIN, Sao Paulo, May 2020, LNCS vol. 12118.
25. Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz. Tight Bounds on Subexponential Time Ap-proximation of Set Cover and Related Problems. In WAOA, September 2020, Springer LNCS, June 2021.
26. Ívar Marrow Arnthorsson, Steven Chaplick, Jökull Snær Gylfason, Magnús M. Halldórsson, Jökull Máni Reynisson, Tigran Tonoyan. Generalized Disk Graphs. In ´ WADS : 115-128, August 2021.

Invited Conference Papers and Book Chapters
27. Magnús M. Halldórsson and Roger Wattenhofer. Wireless Network Algorithmics. Computing and Software Science - State of the Art and Perspectives. (Bernhard Steffen, Gerhard J. Woeginger, eds.) Lecture Notes in Computer Science 10000, pp. 141-160, Springer 2019.

Reports
1. Christina Fragouli, Magnús M. Halldórsson, Kyle Jamieson and Bhaskar Krishnamachari. Foundations of Wireless Networking (Dagstuhl Seminar 17271). Dagstuhl Reports 7(7), 2018.
2. Magnús M. Halldórsson, Nicole Megow and Clifford Stein, Scheduling (Dagstuhl Seminar 18101). Dagstuhl Reports 8(3), https://doi.org/10.4230/DagRep.8.3.1, 2018.

Invited Plenary Talks
2019 (Keynote) 14th International Conference on Distributed Computing in Sensor Systems (DCOSS), Santorini, Greece, May 2019.
2018 Highlights of Algorithms (HALG), Amsterdam, June 2018.
2017 (Tutorial) 6th Workshop on Advances in Distributed Graph Algorithms (ADGA), Vienna, Oct. 2017.

Heiti verkefnis: Nýjar víddir í reikniritum fyrir þráðlaus net/Post-modern models of wireless algorithms
Verkefnisstjóri: Magnús Már Halldórsson, Háskólanum í Reykjavík
Tegund styrks: Verkefnisstyrkur
Styrktímabil: 2017-2019
Fjárhæð styrks kr. 48.068.000
Tilvísunarnúmer Rannís: 174484