List of PODC 2022 accepted papers with links

The list of accepted papers for PODC 2022 is out, see here. Below is the same list but with links to the papers when available. I have seen people do this for other conferences, and I think it is useful. For any comment, send me an email. If there is additional material (e.g. blog posts, recorded talks) I will also add links to them.

• A Framework for Distributed Quantum Queries in the CONGEST Model. T. de Vos, J. van Apeldoorn. pdf, arxiv page.

• Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication. A. Korman, R. Vacus. pdf, arxiv page.

• What can be certified compactly?. L. Feuilloley, N. Bousquet, T. Pierron. pdf, arxiv page.

• Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees. A. Appan, A. Chandramouli, A. Choudhury. pdf, arxiv page.

• When is Recoverable Consensus Harder Than Consensus? C. Delporte-Gallet, P. Fatourou, H. Fauconnier, E. Ruppert. pdf, arxiv page.

• Node and Edge Averaged Complexities of Local Graph Problems. A. Balliu, M. Ghaffari, F. Kuhn, D. Olivetti.

• The Space Complexity of Consensus from Swap. S. Ovens.

• State Complexity of Protocols With Leaders. J. Leroux. pdf, arxiv page.

• Narrowing the LOCAL – CONGEST Gaps in Sparse Networks via Expander Decompositions. Y. Chang, H. Su. pdf, arxiv page.

• A Recursive Early-Stopping Phase King Protocol. C. Lenzen, S. Sheikholeslami. pdf.

• Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement. I. Abraham, N. Ben-David, S. Yandamuri. pdf,

• Universally-Optimal Distributed Exact Min-Cut. M. Ghaffari, G. Zuzic. pdf, arxiv page.

• Distributed Computations in Fully-Defective Networks. K. Censor-Hillel, S. Cohen, R. Gelles, G. Sela. pdf, arxiv page.

• A Distributed Combinatorial Topology Approach to Arrow’s Impossibility. S. Rajsbaum, A. Raventós-Pujol. pdf.

• Deterministic Near-Optimal Distributed Listing of Cliques. K. Censor-Hillel, D. Leitersdorf, D. Vulakh. pdf, arxiv page.

• Near-Optimal Leader Election in Population Protocols on Graphs. D. Alistarh, J. Rybicki, S. Voitovych. pdf, arxiv page.

• The Laplacian Paradigm in the Broadcast Congested Clique. T. de Vos, S. Forster. pdf, arxiv page.

• Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs. M. Dory, M. Ghaffari, S. Ilchi. pdf, arxiv page.

• Overcoming Congestion in Distributed Coloring. M. Halldorsson, A. Nolin, T. Tonoyan. pdf, arxiv page.

• Constant-Round Near-Optimal Spanners in Congested Clique. S. Chechik, T. Zhang.

• Distributed Edge Coloring in Time Polylogarithmic in Δ. A. Balliu, S. Brandt, F. Kuhn, D. Olivetti. pdf, arxiv page.

• Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks. X. Wu, P. Yao. pdf, arxiv page.

• Optimal Synchronous Approximate Agreement with Asynchronous Fallback. D. Ghinea, C. Liu-Zhang, R. Wattenhofer. pdf.

• From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good. S. Rajakrishnan, R. Agarwal, D. Shmoys. pdf.

• Optimal Clock Synchronization with Signatures. C. Lenzen, J. Loss. pdf, arxiv page.

• Parameterized Verification under Release Acquire is PSPACE-complete. S. Krishna, A. Godbole, R. Meyer, S. Chakraborty.

• Blunting an Adversary Against Randomized Concurrent Programs with Linearizable Implementations. H. Attiya, C. Enea, J. Welch. pdf, arxiv page.

• Population Protocols for Exact Plurality Consensus. G. Bankhamer, P. Berenbrink, F. Biermeier, R. Elsässer, H. Hosseinpour, D. Kaaser, P. Kling.

• Fast and Fair Lock-Free Locks. N. Ben-David, G. Blelloch. pdf, arxiv page.

• A Massively Parallel Modularity-Maximizing Algorithm With Provable Guarantees. V. Cohen-Addad, F. Mallmann-Trenn, D. Saulpic.

• Massively Parallel Computation in a Heterogeneous Regime. O. Fischer, A. Horowitz, R. Oshman.

• Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security. I. Abraham, G. Asharov. pdf.

• The Landscape of Distributed Complexities on Trees and Beyond. C. Grunau, V. Rozhoň, S. Brandt. pdf, arxiv page.

• Can’t See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners. O. Kahalon, H. Le, L. Milenković, S. Solomon. pdf, arxiv page.

• A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement. P. Fraigniaud, A. Paz, S. Rajsbaum. pdf, arxiv page.

• Adaptively Secure Single Secret Leader Election from DDH. D. Catalano, D. Fiore, E. Giunta. pdf.

• Revisiting the Power of Non-Equivocation in Distributed Protocols. N. Ben-David, B. Chan, E. Shi.

• Balanced Allocations with the Choice of Noise. D. Los, T. Sauerwald. pdf, arxiv page.

• Internet Computer Consensus. J. Camenisch, M. Drijvers, T. Hanke, Y. Pignolet, V. Shoup, D. Williams. pdf.

• Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation. N. Alhaddad, S. Das, S. Duan, L. Ren, M. Varia, Z. Xiang, H. Zhang. pdf.

Brief Announcements

• Brief Announcement: Fault Tolerant Coloring of the Asynchronous Cycle. P. Fraigniaud, P. Lambein-Monette, M. Rabie.

• Brief Announcement: Towards a Theory of Wear Leveling in Persistent Data Structures. X. Liu, W. Golab.

• Brief Announcement: Make Every Word Count: Adaptive BA with Fewer Words. S. Cohen, I. Keidar, A. Spiegelman. pdf, arxiv page.

• Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds. J. Augustine, W. Moses Jr., G. Pandurangan. pdf, arxiv page.

• Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear. A. El-Hayek, M. Henzinger, S. Schmid.

• Brief Announcement: Asynchronous Randomness and Consensus without Trusted Setup. L. De Souza, P. Kuznetsov, A. Tonkikh.

• Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer. L. Tseng, Q. Zhang.

• Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets. S. Pai, S. Pemmaraju. pdf, arxiv page.

• Brief Announcement: Deterministic Consensus and Checkpointing with Crashes: Time and Communication Efficiency. B. Chlebus, D. Kowalski, J. Olkowski.

• Brief Announcement: The weakest failure detector for genuine atomic multicast. P. Sutra.

• Brief Announcement: How to Tame Multiple Spending in Decentralized Cryptocurrencies. J. Bezerra de Araújo, P. Kuznetsov. pdf, arxiv page.

• Brief Announcement: Gathering despite a linear number of weakly Byzantine agents. J. Hirose, J. Nakamura, F. Ooshita, M. Inoue. pdf, arxiv page.

• Brief Announcement: Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model. V. Manoharan, V. Ramachandran. pdf, arxiv page.

• Brief Announcement: (1+ϵ)-Approximate Shortest Paths in Dynamic Streams. C. Trehan, M. Elkin. pdf, arxiv page.

• Brief Announcement: A Hierarchy of Time-Bounded Local Decision. E. Tshuva, R. Oshman.

• Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver. I. Anagnostides, C. Lenzen, B. Haeupler, G. Zuzic, T. Gouleakis.

• Brief Announcement: Probabilistic Dynamic Input/Output Automata. P. Civit, M. Potop-Butucaru. a pdf

• Brief Announcement: Holistic Verification of Blockchain Consensus. N. Bertrand, V. Gramoli, M. Lazic, I. Konnov, P. Tholoniat, J. Widder. pdf, arxiv page.

• Brief Announcement: Asynchronous Verifiable Information Dispersal with Near-Optimal Communication. N. Alhaddad, S. Das, S. Duan, L. Ren, M. Varia, Z. Xiang, H. Zhang. pdf.