Here you can find the the Paper Awards and the Sirocco Prize.
Best paper awards
Best paper award shared by:
- Lila Fontes, Mathieu Laurière, Sophie Laplante and Alexandre Nolin. The communication complexity of functions with large outputs.
- Stefan Schmid, Jakub Svoboda and Michelle Yeo. Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.
Best student paper award shared by:
- Abir Islam, graduate student at the University of New Mexico, for the paper: Abir Islam, Jared Saia and Varsha Dani. Boundary Sketching With Asymptotically Optimal Distance and Rotation.
- Sameep Dahal, graduate student at Aalto University, Finland, for the paper: Sameep Dahal and Jukka Suomela. Distributed Half-Integral Matching and Beyond.
2023 Sirocco Prize
|Boaz Patt-Shamir (Tel-Aviv University, Israel) — For his outstanding contributions to distributed computing under bandwidth limitations.
It is our pleasure to award the 2023 SIROCCO Prize for Innovation in Distributed Computing to Boaz Patt-Shamir, professor at Tel-Aviv University, Israel, for his outstanding contributions to distributed computing under bandwidth limitations.
Boaz Patt-Shamir is one of the main contributors to distributed network computing, especially regarding solving graph problems efficiently under the constraint that nodes can exchange a limited information with their neighbors in each round. Typical problems addressed in Boaz Patt-Shamir’s papers are routing, matching, shortest paths, sorting, and checkability, to mention just a few. They also include problems motivated by applications such as sensor networks, recommendation systems, peer-to-peer applications, etc.
Indeed, since the work by J. Garay, S. Kutten, D. Peleg, and V. Rubinovich (SIAM J. of Computing, 1998 and 2000), it was known that constructing a minimum-weight spanning tree (MST) can be done in roughly O(D + √n) rounds in n-node networks with diameter D = Ω (log n) when the nodes are restricted to exchange O(log n)-bit messages in each round. It was also known that this bound is essentially tight. In his PODC 2001 paper, Boaz Patt-Shamir et al. proved that an nΩ(1) lower bound also holds in networks with constant diameter, specifically Õ(√n) rounds in networks with diameter 4, and Õ(n1/4) rounds in networks with diameter 3. In contrast, the same paper shows that, in graphs with diameter 2, MST can be solved in O(log n) rounds, hence establishing an exponential gap between the computing power of networks with diameter 3 and those with diameter 2. Another exponential gap is established in the SPAA 2003 paper, in which Boaz Patt- Shamir et al. proved that MST can be solved in just O(loglogn) rounds in cliques. The model introduced in the SPAA 2003 paper is now commonly referred to as the Congested Clique model, which completes the trio of core models for distributed network computing, now known as LOCAL, CONGEST, and Congested Clique.
The 2023 Award committee:1
Paola Flocchini (University of Ottawa, Canada)
1 We wish to thank the nominators for the nomination and for contributing heavily to this text.