{"id":152,"date":"2020-06-23T11:06:26","date_gmt":"2020-06-23T15:06:26","guid":{"rendered":"http:\/\/www.podc.org\/podc2020\/?page_id=152"},"modified":"2021-10-29T10:41:01","modified_gmt":"2021-10-29T14:41:01","slug":"program","status":"publish","type":"page","link":"https:\/\/www.podc.org\/podc2020\/program\/","title":{"rendered":"PODC 2020 Program"},"content":{"rendered":"<p style=\"text-align: center;\">3-6 August 2020, Virtual conference<br \/>\n<a href=\"http:\/\/www.podc.org\/\">www.podc.org<\/a> and <span class=\"citation\" data-cites=\"podc_disc\">@podc_disc on twitter<\/span><\/p>\n<h1 id=\"format\">Format<\/h1>\n<p>PODC 2020 is held online as a virtual event.<\/p>\n<p>Every paper\u2019s talk is pre-recorded and about 20\u202625min. These talks will be available online, e.g., in a dedicated Youtube Channel. Second, during each conference session, there are live 5-min presentations (3 min for BAs) on each paper, followed by Q&amp;A, and followed by a common discussion among a \u201cpanel\u201d of the presenters and the audience. An additional chat is organized for 1-1 exchanges. Each such session takes about 1h.<\/p>\n<h1 id=\"overview\">Overview<\/h1>\n<p>A 4h-slot is allocated for the online meeting on four days, August 3-6, during the week planned for PODC.<\/p>\n<ul>\n<li>Start: 15:00 CEST, 06:00 Pacific, 09:00 Eastern, 13:00 UTC, 22:00 JPN<\/li>\n<li>End: 19:00 CEST, 10:00 Pacific, 13:00 Eastern, 17:00 UTC, 02:00 JPN<\/li>\n<\/ul>\n<h1 id=\"schedule\">Schedule<\/h1>\n<ul>\n<li>Monday, August 3\n<ul>\n<li>15:00-16:30 CEST Opening, Keynote by Rachid Guerraoui, Q&amp;A<\/li>\n<li>16:45-17:45 CEST Session: Concurrency<\/li>\n<li>18:00-19:00 CEST Session: Graph Algorithms I<\/li>\n<\/ul>\n<\/li>\n<li>Tuesday, August 4\n<ul>\n<li>15:00-16:00 CEST Session: Consensus<\/li>\n<li>16:15-17:15 CEST Session: Concurrency, Self-* Algorithms and more<\/li>\n<li>17:30-19:00 CEST Awards session and business meeting<\/li>\n<\/ul>\n<\/li>\n<li>Wednesday, August 5\n<ul>\n<li>15:00-16:30 CEST Keynote by James Aspnes and Q&amp;A<\/li>\n<li>16:45-17:45 CEST Session: Wireless Protocols and Graph Models<\/li>\n<li>18:00-19:00 CEST Session: Graph Algorithms II<\/li>\n<\/ul>\n<\/li>\n<li>Thursday, August 6\n<ul>\n<li>15:00-16:30 CEST Session: Byzantine Attacks and Consensus<\/li>\n<li>16:45-17:45 CEST Session: Coordination<\/li>\n<li>18:00-19:00 CEST Session: Graph Algorithms and CONGEST Model<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h1 id=\"detailed-schedule\">Detailed Schedule<\/h1>\n<h2 id=\"mon-august-3\">Monday, August 3<\/h2>\n<h3>Opening and Keynote<br \/>\n15:00-16:30 CEST<\/h3>\n<p>Session chair: Yuval Emek<\/p>\n<ul>\n<li><strong>Keynote<\/strong>: &#8220;Journeys to the Center of Distributed Computing&#8221; (video)\n<ul>\n<li>Rachid Guerraoui<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Concurrency<br \/>\n16:45-17:45 CEST<\/h3>\n<p>Session chair: Lewis Tseng<\/p>\n<ul>\n<li><strong>Best Student Paper<\/strong>: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405739\">An Adaptive Approach to Recoverable Mutual Exclusion<\/a> (<a href=\"https:\/\/youtu.be\/_g2WFDFvO6Y\">video<\/a>)\n<ul>\n<li>Sahil Dhoked (The University of Texas at Dallas)<\/li>\n<li>Neeraj Mittal (The University of Texas at Dallas)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405725\">Upper and Lower Bounds on the Space Complexity of Detectable Objects<\/a> (<a href=\"https:\/\/youtu.be\/0NgDiDYcRSg\">video<\/a>)\n<ul>\n<li>Ohad Ben-Baruch (Ben-Gurion University)<\/li>\n<li>Danny Hendler (Ben-Gurion University)<\/li>\n<li>Matan Rusanovsky (Ben-Gurion University &amp; Israel Atomic Energy Commission)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405723\">Extending the Wait-free Hierarchy to Multi-Threaded Systems<\/a> (<a href=\"https:\/\/youtu.be\/PjWRqhEzqeE\">video<\/a>)\n<ul>\n<li>Matthieu Perrin (LS2N, Universit\u00e9 de Nantes)<\/li>\n<li>Achour Most\u00e9faoui (LS2N, Universit\u00e9 de Nantes)<\/li>\n<li>Gr\u00e9goire Bonin (LS2N, Universit\u00e9 de Nantes)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3406005\">Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity<\/a> (<a href=\"https:\/\/youtu.be\/ZMwHQ39stPE\">video<\/a>)\n<ul>\n<li>Ahad Mirza Baig (IST Austria)<\/li>\n<li>Danny Hendler (Ben-Gurion University)<\/li>\n<li>Alessia Milani (LaBRI &#8211; Bordeaux INP)<\/li>\n<li>Corentin Travers (LABRI &#8211; Bordeaux INP)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405727\">From Bezout\u2019s Identity to Space-Optimal Election in Anonymous Memory Systems<\/a> (<a href=\"https:\/\/youtu.be\/uawi8qeXSVI\">video<\/a>)\n<ul>\n<li>Emmanuel Godard (Aix-Marseille University)<\/li>\n<li>Damien Imbs (Aix-Marseille University)<\/li>\n<li>Michel Raynal (IRISA)<\/li>\n<li>Gadi Taubenfeld (IDC)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405709\">Store-Collect in the Presence of Continuous Churn with Application to Snapshots and Lattice Agreement<\/a> (<a href=\"https:\/\/youtu.be\/CIOwCkpSnwg\">video<\/a>)\n<ul>\n<li>Hagit Attiya, Sweta Kumari (Technion)<\/li>\n<li>Archit Somani (Technion)<\/li>\n<li>Jennifer LWelch (TAMU)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405743\">Why Extension-Based Proofs Fail<\/a> (<a href=\"https:\/\/youtu.be\/nWGp2C9FMP8\">video<\/a>)\n<ul>\n<li>Faith Ellen (University of Toronto)<\/li>\n<li>Dan Alistarh (IST Austria)<\/li>\n<li>James Aspnes (Yale University)<\/li>\n<li>Leqi Zhu (University of Michigan)<\/li>\n<li>Rati Gelashvili (University of Toronto)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405749\">The Only Undoable CRDTs are Counters<\/a> (<a href=\"https:\/\/youtu.be\/tHl1owpku9M\">video<\/a>)\n<ul>\n<li>Stephen Dolan (OCaml Labs)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Graph Algorithms I<br \/>\n18:00-19:00 CEST<\/h3>\n<p>Session chair: Przemek Uznanski<\/p>\n<ul>\n<li><strong>Best Paper<\/strong>: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405711\">Exponentially Faster Shortest Paths in the Congested Clique<\/a> (<a href=\"https:\/\/youtu.be\/H8x77z62FYA\">video<\/a>)\n<ul>\n<li>Michal Dory (Technion)<\/li>\n<li>Merav Parter (Weizmann Institute)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405745\">Truly Tight-in-Delta Bounds for Bipartite Maximal Matching and Variants<\/a> (<a href=\"https:\/\/youtu.be\/fg-zUSMGYF0\">video<\/a>)\n<ul>\n<li>Sebastian Brandt (ETH Zurich)<\/li>\n<li>Dennis Olivetti (University of Freiburg)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405732\">Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets<\/a> (<a href=\"https:\/\/youtu.be\/Do9w6GTUsgE\">video<\/a>)\n<ul>\n<li>Sepehr Assadi (Rutgers University)<\/li>\n<li>Gillat Kol (Princeton University)<\/li>\n<li>Rotem Oshman (Tel Aviv University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405721\">Seeing Far vs Seeing Wide: Volume Complexity of Local Graph Problems<\/a> (<a href=\"https:\/\/youtu.be\/rz65TrtjUmk\">video<\/a>)\n<ul>\n<li>Will Rosenbaum (Amherst College)<\/li>\n<li>Jukka Suomela (Aalto University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405718\">Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity<\/a> (<a href=\"https:\/\/youtu.be\/GGcIkUcvTbA\">video<\/a>)\n<ul>\n<li>Soumyottam Chatterjee (Georgetown University)<\/li>\n<li>Robert Gmyr (Microsoft)<\/li>\n<li>Gopal Pandurangan (University of Houston)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405719\">Computing Shortest Paths and Diameter in the Hybrid Network Model<\/a> (<a href=\"https:\/\/youtu.be\/5d6OlbXQ6iQ\">video<\/a>)\n<ul>\n<li>Philipp Schneider (University of Freiburg)<\/li>\n<li>Fabian Kuhn (University of Freiburg)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405737\">Massively Parallel Algorithms for Minimum Cut<\/a> (<a href=\"https:\/\/youtu.be\/snWd9TyACkc\">video<\/a>)\n<ul>\n<li>Mohsen Ghaffari (ETH Zurich)<\/li>\n<li>Krzysztof Nowicki (University of Wroclaw)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h2 id=\"tue-august-4\">Tuesday, August 4<\/h2>\n<h3 id=\"cest-session-consensus\">Session: Consensus<br \/>\n15:00-16:00 CEST<\/h3>\n<p>Session chair: Robert Els\u00e4sser<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405707\">Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited<\/a> (<a href=\"https:\/\/youtu.be\/uzDTgrDdsZU\">video<\/a>)\n<ul>\n<li>Yuan Lu (New Jersey Institute of Technology)<\/li>\n<li>Zhenliang Lu, Qiang Tang (New Jersey Institute of Technology<\/li>\n<li>JDD-NJIT-ISCAS Joint Blockchain Lab)<\/li>\n<li>Guiling Wang (New Jersey Institute of Technology)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405722\">Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience<\/a> (<a href=\"https:\/\/youtu.be\/CFSXXwYXK5E\">video<\/a>)\n<ul>\n<li>Ittai Abraham (VMware Research)<\/li>\n<li>Danny Dolev (Hebrew University)<\/li>\n<li>Gilad Stern (Hebrew University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405724\">Asynchronous Byzantine Approximate Consensus in Directed Networks<\/a> (<a href=\"https:\/\/youtu.be\/zRaejM7_ekw\">video<\/a>)\n<ul>\n<li>Dimitris Sakavalas (Boston College)<\/li>\n<li>Lewis Tseng (Boston College)<\/li>\n<li>Nitin H. Vaidya (Georgetown University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405731\">On the Subject of Non-Equivocation<\/a> (<a href=\"https:\/\/youtu.be\/Ljayjau9-E0\">video<\/a>)\n<ul>\n<li>Mads Frederik Madsen (IT University of Copenhagen)<\/li>\n<li>S\u00f8ren Debois (IT University of Copenhagen)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3404503\">Almost-surely Terminating Asynchronous Byzantine Agreement Protocols with a Constant Expected Running Time<\/a> (<a href=\"https:\/\/youtu.be\/gQJOPrQDRz0\">video<\/a>)\n<ul>\n<li>Ashish Choudhury (IIIT Bangalore)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405700\">On the Significance of Consecutive Ballots in Paxos<\/a> (<a href=\"https:\/\/youtu.be\/dW187axDPyc\">video<\/a>)\n<ul>\n<li>Eli Goldweber (University of Michigan)<\/li>\n<li>Nuda Zhang (University of Michigan)<\/li>\n<li>Manos Kapritsos (University of Michigan)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405708\">Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP<\/a> (<a href=\"https:\/\/youtu.be\/WzbR-w-lJH0\">video<\/a>)\n<ul>\n<li>Shir Cohen (Technion)<\/li>\n<li>Idit Keidar (Technion)<\/li>\n<li>Alexander Spiegelman (Novi)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405740\">Byzantine Agreement with Unknown Participants and Failures<\/a> (<a href=\"https:\/\/youtu.be\/rkUkFeKYcdQ\">video<\/a>)\n<ul>\n<li>Pankaj Khanchandani (ETH Zurich)<\/li>\n<li>Roger Wattenhofer (ETH Zurich)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Concurrency, Self-* Algorithms and more<br \/>\n16:15-17:15 CEST<\/h3>\n<p>Session chair: Christoph Lenzen<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405736\">Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives<\/a> (<a href=\"https:\/\/youtu.be\/dN-Rj2s-unA\">video<\/a>)\n<ul>\n<li>David Yu Cheng Chan (University of Calgary)<\/li>\n<li>Philipp Woelfel (University of Calgary)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405747\">An O(log3\/2 n) Parallel Time Population Protocol for Majority with O(logn) States<\/a> (<a href=\"https:\/\/youtu.be\/LtnBEKtPpAg\">video<\/a>)\n<ul>\n<li>Stav Ben-Nun (Bar-Ilan University)<\/li>\n<li>Tsvi Kopelowitz (Bar-Ilan University)<\/li>\n<li>Matan Kraus (Bar-Ilan University)<\/li>\n<li>Ely Porat (Bar-Ilan University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405698\">Fine-grained Analysis on Fast Implementations of Distributed Multi-writer Atomic Registers<\/a> (<a href=\"https:\/\/youtu.be\/P7nMZC_Sg-4\">video<\/a>)\n<ul>\n<li>Kaile Huang (Nanjing University)<\/li>\n<li>Yu Huang (Nanjing University)<\/li>\n<li>Hengfeng Wei (Nanjing University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405733\">Self-Stabilizing Leader Election in Regular Graphs<\/a> (<a href=\"https:\/\/youtu.be\/_9-U-WGAkbE\">video<\/a>)\n<ul>\n<li>Hsueh-Ping Chen (Department of Electrical Engineering, National Taiwan University)<\/li>\n<li>Ho-Lin Chen (Department of Electrical Engineering, National Taiwan University)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405726\">Optimal Time and Space Leader Election in Population Protocols<\/a> (<a href=\"https:\/\/youtu.be\/CfLV1b6yOm8\">video<\/a>)\n<ul>\n<li>Petra Berenbrink (Universit\u00e4t Hamburg)<\/li>\n<li>George Giakkoupis (INRIA)<\/li>\n<li>Peter Kling (Universit\u00e4t Hamburg)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405712\">Intermediate Value Linearizability: A Quantitative Correctness Criterion<\/a> (<a href=\"https:\/\/youtu.be\/WfJvWbsTKaM\">video<\/a>)\n<ul>\n<li>Arik Rinberg (Technion)<\/li>\n<li>Idit Keidar (Technion)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405746\">On Implementing Software Transactional Memory in the C++ Memory Model<\/a> (<a href=\"https:\/\/youtu.be\/E6nbzl3nmbk\">video<\/a>)\n<ul>\n<li>Matthew Rodriguez (Lehigh University)<\/li>\n<li>Michael Spear (Lehigh University)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3404502\">Self-stabilizing Systems in Spite of High Dynamics<\/a> (<a href=\"https:\/\/youtu.be\/1k3WOwsmINc\">video<\/a>)\n<ul>\n<li>Karine Altisen (VERIMAG)<\/li>\n<li>St\u00e9phane Devismes (VERIMAG)<\/li>\n<li>Ana\u00efs Durand (LIMOS)<\/li>\n<li>Colette Johnen (CNRS and UnivBordeaux, LaBRI, Talence, France)<\/li>\n<li>Franck Petit (LIP6)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405738\">Hazard Pointer Protection of Structures with Immutable Links<\/a> (<a href=\"https:\/\/youtu.be\/HYCPN6Kp_Ao\">video<\/a>)\n<ul>\n<li>Maged M. Michael (Facebook)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Awards session and business meeting<br \/>\n17:30-19:00 CEST<\/h3>\n<p>Session chair: Jennifer Welch<\/p>\n<h2 id=\"wed-august-5\">Wednesday, August 5<\/h2>\n<h3 id=\"cest-keynote\">Keynote<br \/>\n15:00-16:30 CEST<\/h3>\n<p>Session chair: Christian Cachin<\/p>\n<ul>\n<li><strong>Keynote<\/strong>: &#8220;Population Protocols&#8221; (video)\n<ul>\n<li>James Aspnes<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Wireless Protocols and Graph Models<br \/>\n16:45-17:45 CEST<\/h3>\n<p>Session chair: Andr\u00e9a Richa<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405706\">Distance-2 Coloring in the CONGEST Model<\/a> (<a href=\"https:\/\/youtu.be\/16ioroCGEwU\">video<\/a>)\n<ul>\n<li>Magnus M. Halldorsson (Reykjavik University)<\/li>\n<li>Fabian Kuhn (Freiburg University)<\/li>\n<li>Yannic Maus (Technion)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3404504\">Efficient Deterministic Distributed Coloring with Small Bandwidth<\/a> (<a href=\"https:\/\/youtu.be\/OKcnoHB5CH4\">video<\/a>)\n<ul>\n<li>Philipp Bamberger (University of Freiburg)<\/li>\n<li>Fabian Kuhn (University of Freiburg)<\/li>\n<li>Yannic Maus (Technion)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405693\">Want to Gather? No Need to Chatter!<\/a> (<a href=\"https:\/\/youtu.be\/kWPWFhgaboU\">video<\/a>)\n<ul>\n<li>S\u00e9bastien Bouchard (Universit\u00e9 du Qu\u00e9bec en Outaouais &amp; Sorbonne Universit\u00e9, CNRS, Inria, LIP6 UMR)<\/li>\n<li>Yoann Dieudonn\u00e9 (MIS Lab., Universit\u00e9 de Picardie Jules Verne)<\/li>\n<li>Andrzej Pelc (Universit\u00e9 du Qu\u00e9bec en Outaouais)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405720\">Tight Analysis of Asynchronous Rumor Spreading in Dynamic Networks<\/a> (<a href=\"https:\/\/youtu.be\/k9YnmCL9Hjo\">video<\/a>)\n<ul>\n<li>Ali Pourmiri (Macquarie University)<\/li>\n<li>Bernard Mans (Macquarie University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405713\">The Energy Complexity of BFS in Radio Networks<\/a> (<a href=\"https:\/\/youtu.be\/CaaMHpW-oAU\">video<\/a>)\n<ul>\n<li>Yi-Jun Chang (ETH Z\u00fcrich)<\/li>\n<li>Varsha Dani (University of New Mexico)<\/li>\n<li>Thomas PHayes (University of New Mexico)<\/li>\n<li>Seth Pettie (University of Michigan)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405728\">Improved Distributed Approximations for Maximum-Weight Independent Set<\/a> (<a href=\"https:\/\/youtu.be\/9FGDi3I8oyM\">video<\/a>)\n<ul>\n<li>Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo)<\/li>\n<li>Seri Khoury (UC Berkeley)<\/li>\n<li>Aaron Schild (University of Washington)<\/li>\n<li>Gregory Schwartzman (National Institute of Informatics, Japan)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405697\">Resource Competitive Broadcast against Adaptive Adversary in Multi-channel Radio Networks<\/a> (<a href=\"https:\/\/youtu.be\/ca5Ijo1zIUU\">video<\/a>)\n<ul>\n<li>Haimin Chen (Nanjing University)<\/li>\n<li>Chaodong Zheng (Nanjing University)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Graph Algorithms II<br \/>\n18:00-19:00 CEST<\/h3>\n<p>Session chair: Ami Paz<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405710\">Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta<\/a> (<a href=\"https:\/\/youtu.be\/nctwZfHdV70\">video<\/a>)\n<ul>\n<li>Alkida Balliu, Fabian Kuhn (University of Freiburg)<\/li>\n<li>Dennis Olivetti (University of Freiburg)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405742\">On Distributed Listing of Cliques<\/a> (<a href=\"https:\/\/youtu.be\/NTEESFhGYfc\">video<\/a>)\n<ul>\n<li>Keren Censor-Hillel (Technion)<\/li>\n<li>Fran\u00e7ois Le Gall (Nagoya University)<\/li>\n<li>Dean Leitersdorf (Technion)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405715\">How much does randomness help with locally checkable problems?<\/a> (<a href=\"https:\/\/youtu.be\/aGWgP95b72g\">video<\/a>)\n<ul>\n<li>Alkida Balliu (University of Freiburg)<\/li>\n<li>Sebastian Brandt (ETH Zurich)<\/li>\n<li>Dennis Olivetti (University of Freiburg)<\/li>\n<li>Jukka Suomela (Aalto University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3404505\">Compact Distributed Certification of Planar Graphs<\/a> (<a href=\"https:\/\/youtu.be\/J428OKdCYDE\">video<\/a>)\n<ul>\n<li>Laurent Feuilloley (Universidad de Chile, Chile)<\/li>\n<li>Pierre Fraigniaud (CNRS and Universit\u00e9 de Paris, France)<\/li>\n<li>Pedro Montealegre (Universidad Adolfo Ibanez, Chile)<\/li>\n<li>Ivan Rapaport (Universidad de Chile, Chile)<\/li>\n<li>Eric R\u00e9mila (University of Saint-Etienne, France)<\/li>\n<li>Ioan Todinca (University of Orl\u00e9ans, France)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405730\">Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lov\u00e1sz Local Lemma<\/a> (<a href=\"https:\/\/youtu.be\/_EdZiKLcy-k\">video<\/a>)\n<ul>\n<li>Sebastian Brandt (ETH Zurich)<\/li>\n<li>Christoph Grunau (ETH Zurich)<\/li>\n<li>Vaclav Rozhon (ETH Zurich)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405714\">Multiple Source Replacement Path Problem<\/a> (<a href=\"https:\/\/youtu.be\/sdl5BRsTXUM\">video<\/a>)\n<ul>\n<li>Manoj Gupta (IIT Gandhinagar)<\/li>\n<li>Rahul Jain (IIT Gandhinagar)<\/li>\n<li>Nitiksha Modi (IIT Gandhinagar)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405703\">Classification of distributed binary labeling problems<\/a> (<a href=\"https:\/\/youtu.be\/bbZ4wSDAhUA\">video<\/a>)\n<ul>\n<li>Alkida Balliu (University of Freiburg)<\/li>\n<li>Sebastian Brandt (ETH Zurich)<\/li>\n<li>Yuval Efron (Technion)<\/li>\n<li>Juho Hirvonen (Aalto University)<\/li>\n<li>Yannic Maus (Technion)<\/li>\n<li>Dennis Olivetti (University of Freiburg)<\/li>\n<li>Jukka Suomela (Aalto University)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405694\">Round eliminator: a tool for automatic speedup simulation<\/a> (<a href=\"https:\/\/youtu.be\/288lqVrtyZQ\">video<\/a>)\n<ul>\n<li>Dennis Olivetti (University of Freiburg)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h2 id=\"thu-august-6\">Thursday, August 6<\/h2>\n<h3>Session: Byzantine Attacks and Consensus<br \/>\n15:00-16:30 CEST<\/h3>\n<p>Session chair: Bernardo David<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405695\">Genuinely Distributed Byzantine Machine Learning<\/a> (<a href=\"https:\/\/youtu.be\/zZMqgsHUjYY\">video<\/a>)\n<ul>\n<li>El-Mahdi El-Mhamdi (EPFL)<\/li>\n<li>Rachid Guerraoui (EPFL)<\/li>\n<li>Arsany Guirguis (EPFL)<\/li>\n<li>L\u00ea Nguy\u00ean Hoang (EPFL)<\/li>\n<li>S\u00e9bastien Rouault (EPFL)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405748\">Fault-Tolerance in Distributed Optimization: The Case of Redundancy<\/a> (<a href=\"https:\/\/youtu.be\/SUv4sqRIdhg\">video<\/a>)\n<ul>\n<li>Nirupam Gupta (Georgetown University)<\/li>\n<li>Nitin H. Vaidya (Georgetown University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405734\">Probably Approximately Knowing<\/a> (<a href=\"https:\/\/youtu.be\/WsQ2Gw18RWw\">video<\/a>)\n<ul>\n<li>Yoram Moses (Technion)<\/li>\n<li>Nitzan Zamir (Technion)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3406506\">Positive Aging Admits Fast Asynchronous Plurality Consensus<\/a> (<a href=\"https:\/\/youtu.be\/vcCfwUYp_XM\">video<\/a>)\n<ul>\n<li>Gregor Bankhamer (University of Salzburg)<\/li>\n<li>Robert Els\u00e4sser (University of Salzburg)<\/li>\n<li>Dominik Kaaser (University of Hamburg)<\/li>\n<li>Matja\u017e Krnc (University of Primorska)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405752\">K set-agreement bounds in round-based models through combinatorial topology<\/a> (<a href=\"https:\/\/youtu.be\/jukPuhLTVDs\">video<\/a>)\n<ul>\n<li>Adam Shimi (IRIT, University of Toulouse)<\/li>\n<li>Armando Castaneda (UNAM)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405717\">On Using Null Messages in a Byzantine Setting<\/a> (<a href=\"https:\/\/youtu.be\/p9VWfmQLtf4\">video<\/a>)\n<ul>\n<li>Guy Goren (Technion)<\/li>\n<li>Yoram Moses (Technion)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Coordination<br \/>\n16:45-17:45 CEST<\/h3>\n<p>Session chair: Jared Saia<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405699\">Can Uncoordinated Beeps tell Stories?<\/a> (<a href=\"https:\/\/youtu.be\/jNlZt504inI\">video<\/a>)\n<ul>\n<li>Fabien Dufoulon (Technion &#8211; Israel Institute of Technology)<\/li>\n<li>Janna Burman (Universit\u00e9 Paris-Saclay, CNRS, LRI)<\/li>\n<li>Joffroy Beauquier (Universit\u00e9 Paris-Saclay, CNRS, LRI)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3404501\">Noisy Beeps<\/a> (<a href=\"https:\/\/youtu.be\/OQ9A3sK0k6U\">video<\/a>)\n<ul>\n<li>Klim Efremenko (Ben Gurion University)<\/li>\n<li>Gillat Kol (Princeton University)<\/li>\n<li>Raghuvansh RSaxena (Princeton University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405704\">Perigee: Efficient Peer-to-Peer Network Design for Blockchains<\/a> (<a href=\"https:\/\/youtu.be\/SU1x3bbgarU\">video<\/a>)\n<ul>\n<li>Yifan Mao (The Ohio State University)<\/li>\n<li>Soubhik Deb (University of Washington Seattle)<\/li>\n<li>Shaileshh Bojja Venkatakrishnan (The Ohio State University)<\/li>\n<li>Sreeram Kannan (University of Washington Seattle)<\/li>\n<li>Kannan Srinivasan (The Ohio State University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405716\">DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead<\/a> (<a href=\"https:\/\/youtu.be\/iZPkd1xaMn8\">video<\/a>)\n<ul>\n<li>Seth Gilbert (NUS Singapore)<\/li>\n<li>Gopal Pandurangan (University of Houston)<\/li>\n<li>Peter Robinson (City University of Hong Kong)<\/li>\n<li>Amitabh Trehan (Loughborough University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405744\">Distributed Computation and Reconfiguration in Actively Dynamic Networks<\/a> (<a href=\"https:\/\/youtu.be\/3lHFWnNDTr8\">video<\/a>)\n<ul>\n<li>Othon Michail (University of Liverpool)<\/li>\n<li>George Skretas (University of Liverpool)<\/li>\n<li>Paul Spirakis (University of Liverpool)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405705\">Noisy Beeping Networks<\/a> (<a href=\"https:\/\/youtu.be\/TS261mY51pU\">video<\/a>)\n<ul>\n<li>Yagel Ashkenazi (Bar-Ilan University)<\/li>\n<li>Ran Gelles (Bar-Ilan University)<\/li>\n<li>Amir Leshem (Bar-Ilan University)<\/li>\n<\/ul>\n<\/li>\n<li>Brief Announcement: <a href=\"https:\/\/doi.org\/10.1145\/3382734.3405696\">Deterministic Lower Bound for Dynamic Balanced Graph Partitioning<\/a> (<a href=\"https:\/\/youtu.be\/Fr4850jLHCk\">video<\/a>)\n<ul>\n<li>Maciej Pacut (University of Vienna)<\/li>\n<li>Mahmoud Parham (University of Vienna)<\/li>\n<li>Stefan Schmid (University of Vienna)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Session: Graph Algorithms and CONGEST Model<br \/>\n18:00-19:00 CEST<\/h3>\n<p>Session chair: Alkida Balliu<\/p>\n<ul>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405729\">Single-Source Shortest Paths in the CONGEST Model with Improved Bound<\/a> (<a href=\"https:\/\/youtu.be\/sCDZQbw2h9M\">video<\/a>)\n<ul>\n<li>Shiri Chechik (Tel Aviv University)<\/li>\n<li>Doron Mukhtar (Tel Aviv University)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405701\">Distributed Construction of Light Networks<\/a> (<a href=\"https:\/\/youtu.be\/0LUee3jMcXY\">video<\/a>)\n<ul>\n<li>Michael Elkin (Ben-Gurion University of the Negev)<\/li>\n<li>Arnold Filtser (Columbia University)<\/li>\n<li>Ofer Neiman (Ben-Gurion University of the Negev)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405751\">Simple, Deterministic, Constant-Round Coloring in the Congested Clique<\/a> (<a href=\"https:\/\/youtu.be\/fz7ZIf3Uk_c\">video<\/a>)\n<ul>\n<li>Artur Czumaj (University of Warwick)<\/li>\n<li>Peter Davies (IST Austria)<\/li>\n<li>Merav Parter (Weizmann Institute of Science)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405735\">Efficient and Simple Algorithms for Fault Tolerant Spanners<\/a> (<a href=\"https:\/\/youtu.be\/qV9k-_kzy0g\">video<\/a>)\n<ul>\n<li>Michael Dinitz (Johns Hopkins University)<\/li>\n<li>Caleb Robelle (University of Maryland, Baltimore County)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405750\">Distributed Approximation on Power Graphs<\/a> (<a href=\"https:\/\/youtu.be\/O0BqznC55MQ\">video<\/a>)\n<ul>\n<li>Reuven Bar-Yehuda (Technion)<\/li>\n<li>Keren Censor-Hillel (Technion)<\/li>\n<li>Yannic Maus (Technion)<\/li>\n<li>Shreyas Pai (The University of Iowa)<\/li>\n<li>Sriram VPemmaraju (The University of Iowa)<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/doi.org\/10.1145\/3382734.3405702\">Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST<\/a> (<a href=\"https:\/\/youtu.be\/orzUsqt4JZA\">video<\/a>)\n<ul>\n<li>Yuval Efron (Technion)<\/li>\n<li>Ofer Grossman (MIT)<\/li>\n<li>Seri Khoury (UC Berkeley)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>3-6 August 2020, Virtual conference www.podc.org and @podc_disc on twitter Format PODC 2020 is held online as a virtual event. Every paper\u2019s talk is pre-recorded and about 20\u202625min. These talks will be available online, e.g., in a dedicated Youtube Channel. Second, during each conference session, there are live 5-min presentations (3 min for BAs) on &hellip; <a href=\"https:\/\/www.podc.org\/podc2020\/program\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;PODC 2020 Program&#8221;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-152","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/pages\/152","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/comments?post=152"}],"version-history":[{"count":25,"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/pages\/152\/revisions"}],"predecessor-version":[{"id":218,"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/pages\/152\/revisions\/218"}],"wp:attachment":[{"href":"https:\/\/www.podc.org\/podc2020\/wp-json\/wp\/v2\/media?parent=152"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}