{"id":250,"date":"2016-04-30T08:24:56","date_gmt":"2016-04-30T12:24:56","guid":{"rendered":"http:\/\/www.podc.org\/podc2016\/?page_id=250"},"modified":"2021-10-29T10:38:32","modified_gmt":"2021-10-29T14:38:32","slug":"program","status":"publish","type":"page","link":"https:\/\/www.podc.org\/podc2016\/program\/","title":{"rendered":"PODC 2016 Program"},"content":{"rendered":"<p style=\"text-align: center;\"><a href=\"https:\/\/www.podc.org\/podc2016\/wp-content\/uploads\/sites\/5\/2016\/07\/print-program.pdf\">Printable\u00a0Program<\/a>\u00a0(<a href=\"https:\/\/www.podc.org\/podc2016\/wp-content\/uploads\/sites\/5\/2016\/07\/print-program.pdf\">pdf<\/a>)<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/www.podc.org\/podc2016\/local-arrangements\/\"><strong>UPDATED\u00a0Venue\u00a0Information<\/strong><\/a><\/p>\n<h2>Monday, July 25<\/h2>\n<p>8:00 &#8212; 17:30 <b>Workshops<\/b><\/p>\n<p>16:30 &#8212; 18:00 <a href=\"https:\/\/www.podc.org\/podc2016\/faith-ellen-celebration\/\"><b>Faith Ellen Birthday Celebration<\/b><\/a><\/p>\n<p>18:00 &#8212; 19:30 <b>Reception<\/b><\/p>\n<h2>Tuesday, July 26<\/h2>\n<p>8:30 &#8212; 8:40 <b>Opening<\/b><\/p>\n<p>8:40 &#8212; 9:40 <b>Keynote Lecture 1<\/b><\/p>\n<ul>\n<li><b>New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources<\/b><br \/>\nAndrew A. Chien (The University of Chicago, Argonne National Laboratory)<\/li>\n<\/ul>\n<p>9:40 &#8212; 10:00 <b>Coffee break<\/b><\/p>\n<p>10:00 &#8212; 11:56 <b>Session 1<\/b><br \/>\nSession Chair: Calvin Newport (Georgetown University, USA)<\/p>\n<ul>\n<li>10:00 &#8212; 10:23<br \/>\nA Distributed (2+\u03b5)-Approximation for Vertex Cover in O(log(\u0394)\/\u03b5 log log(\u0394)) Rounds (<b>Best Student Paper Award<\/b>)<br \/>\nReuven Bar-Yehuda, Keren Censor-Hillel and Gregory Schwartzman<\/li>\n<li>10:23 &#8212; 10:46<br \/>\nThe Greedy Spanner is Existentially Optimal (<b>Best Student Paper Award<\/b>)<br \/>\nArnold Filtser and Shay Solomon<\/li>\n<li>10:46 &#8212; 11:09<br \/>\nMST in Log-Star Rounds of Congested Clique<br \/>\nMohsen Ghaffari and Merav Parter<\/li>\n<li>11:09 &#8212; 11:32<br \/>\nDistributed Algorithms for Planar Networks I: Planar Embedding<br \/>\nMohsen Ghaffari and Bernhard Haeupler<\/li>\n<li>11:32 &#8212; 11:38<br \/>\nBrief Announcement: Labeling Schemes for Power-Law Graphs<br \/>\nNoy Rotbart, Casper Petersen, Jakob Grue Simonsen and Christian Wulff-Nilsen<\/li>\n<li>11:38 &#8212; 11:44<br \/>\nBrief Announcement: Sublinear-Space Distance Labeling using Hubs<br \/>\nPawel Gawrychowski, Adrian Kosowski and Przemyslaw Uznanski<\/li>\n<li>11:44 &#8212; 11:50<br \/>\nBrief Announcement: Optimal leader election in multi-hop radio networks<br \/>\nArtur Czumaj and Peter Davies<\/li>\n<li>11:50 &#8212; 11:56<br \/>\nBrief Announcement: The Small World of Curious Beings<br \/>\nSoroush Alamdari<\/li>\n<\/ul>\n<p>12:00 &#8212; 13:30 <b>Lunch<\/b><\/p>\n<p>13:30 &#8212; 15:08 <b>Session 2<\/b><br \/>\nSession Chair: Oksana Denysyuk (University of Calgary, Canada)<\/p>\n<ul>\n<li>13:30 &#8212; 13:53<br \/>\nAnalysing Snapshot Isolation (<b>Best Paper Award<\/b>)<br \/>\nAndrea Cerone and Alexey Gotsman<\/li>\n<li>13:53 &#8212; 14:16<br \/>\nRecoverable Mutual Exclusion<br \/>\nWojciech Golab and Aditya Ramaraju<\/li>\n<li>14:16 &#8212; 14:39<br \/>\nA Randomized Concurrent Algorithm for Disjoint Set Union<br \/>\nSiddhartha V. Jayanti and Robert E. Tarjan<\/li>\n<li>14:39 &#8212; 15:02<br \/>\nSelf-stabilizing Balls &amp; Bins in Batches<br \/>\nPetra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel and Christopher Wastell<\/li>\n<li>15:02 &#8212; 15:08<br \/>\nBrief Announcement: Local Independent Set Approximation<br \/>\nMarijke H. L. Bodlaender, Magnus M. Halldorsson, Christian Konrad and Fabian Kuhn<\/li>\n<\/ul>\n<p>15:10 &#8212; 15:30 <b>Coffee break<\/b><\/p>\n<p>15:30 &#8212; 17:31 <b>Session 3<\/b><br \/>\nSession Chair: Wojciech Golab (University of Waterloo, Canada)<\/p>\n<ul>\n<li>15:30 &#8212; 15:53<br \/>\nDeterministic Objects: Life beyond Consensus<br \/>\nYehuda Afek, Faith Ellen and Eli Gafni<\/li>\n<li>15:53 &#8212; 16:16<br \/>\nUnbeatable Set Consensus via Topological and Combinatorial Reasoning<br \/>\nArmando Casta\u00f1eda, Yannai A. Gonczarowski and Yoram Moses<\/li>\n<li>16:16 &#8212; 16:39<br \/>\nA Polylogarithmic Gossip Algorithm for Plurality Consensus<br \/>\nMohsen Ghaffari and Merav Parter<\/li>\n<li>16:39 &#8212; 17:02<br \/>\nNoisy Rumor Spreading and Plurality Consensus<br \/>\nPierre Fraigniaud and Emanuele Natale<\/li>\n<li>17:02 &#8212; 17:25<br \/>\nRational Consensus: Extended Abstract<br \/>\nJoseph Halpern and Xavier Vila\u00e7a<\/li>\n<li>17:25 &#8212; 17:31<br \/>\nBrief Announcement: A Tight Space Bound for Consensus<br \/>\nLeqi Zhu<\/li>\n<\/ul>\n<p>17:31 &#8211; 19:15 <b>Business Meeting<\/b> (open to all PODC attendees)<\/p>\n<h2>Wednesday, July 27<\/h2>\n<p>8:40 &#8212; 9:40 <b>Keynote Lecture 2<\/b><\/p>\n<ul>\n<li><a href=\"\/data\/podc2016\/FaithEllenInvitedTalk.pptx\"><b>Concurrent Data Structures <\/b><\/a>(<a href=\"\/data\/podc2016\/FaithEllenInvitedTalk.pptx\">slides<\/a>)<br \/>\nFaith Ellen (University of Toronto)<\/li>\n<\/ul>\n<p>9:40 &#8212; 10:00 <b>Coffee break<\/b><\/p>\n<p>10:00 &#8212; 11:56 <b>Session 4<\/b><br \/>\nSession Chair: Andrea Richa (Arizona State, USA)<\/p>\n<ul>\n<li>10:00 &#8212; 10:23<br \/>\nContention Resolution on a Fading Channel<br \/>\nJeremy T. Fineman, Seth Gilbert, Fabian Kuhn and Calvin Newport<\/li>\n<li>10:23 &#8212; 10:46<br \/>\nReliable Communication over Highly Connected Noisy Networks<br \/>\nNoga Alon, Mark Braverman, Klim Efremenko, Ran Gelles and Bernhard Haeupler<\/li>\n<li>10:46 &#8212; 11:09<br \/>\nContention Resolution on Multiple Channels with Collision Detection<br \/>\nJeremy Fineman, Calvin Newport and Tonghe Wang<\/li>\n<li>11:09 &#8212; 11:32<br \/>\nHow Asynchrony Affects Rumor Spreading Time<br \/>\nGeorge Giakkoupis, Yasamin Nazari and Philipp Woelfel<\/li>\n<li>11:32 &#8212; 11:38<br \/>\nBrief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model<br \/>\nYi-Jun Chang, Tsvi Kopelowitz and Seth Pettie<\/li>\n<li>11:38 &#8212; 11:44<br \/>\nBrief Announcement: Data Dissemination in Unified Dynamic Wireless Networks<br \/>\nMagnus M. Halldorsson, Tigran Tonoyan, Yuexuan Wang and Dongxiao Yu<\/li>\n<li>11:44 &#8212; 11:50<br \/>\nBrief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries<br \/>\nAris Pagourtzis, Giorgos Panagiotakos and Dimitris Sakavalas<\/li>\n<li>11:50 &#8212; 11:56<br \/>\nBrief Announcement: Self-Stabilizing Clock Synchronization with 3-bit messages<br \/>\nLucas Boczkowski, Amos Korman and Emanuele Natale<\/li>\n<\/ul>\n<p>12:00 &#8212; 13:30 <b>Lunch<\/b><\/p>\n<p>13:30 &#8212; 15:08 <b>Session 5<\/b><br \/>\nSession Chair: Merav Parter (MIT, USA)<\/p>\n<ul>\n<li>13:30 &#8212; 13:53<br \/>\nDistributed Strong Diameter Network Decomposition<br \/>\nMichael Elkin and Ofer Neiman<\/li>\n<li>13:53 &#8212; 14:16<br \/>\nOptimal Dynamic Distributed MIS<br \/>\nKeren Censor-Hillel, Elad Haramaty and Zohar Karnin<\/li>\n<li>14:16 &#8212; 14:39<br \/>\nA Local Constant Factor MDS Approximation for Bounded Genus Graphs<br \/>\nSaeed Akhoondian Amiri, Stefan Schmid and Sebastian Siebertz<\/li>\n<li>14:39 &#8212; 15:02<br \/>\nOn Efficient Distributed Construction of Near Optimal Routing Schemes<br \/>\nMichael Elkin and Ofer Neiman<\/li>\n<li>15:02 &#8212; 15:08<br \/>\nBrief anouncement: Deterministic Graph Connectivity in the Broadcast Congested Clique<br \/>\nPedro Montealegre and Ioan Todinca<\/li>\n<\/ul>\n<p>15:10 &#8212; 15:30 <b>Coffee break<\/b><\/p>\n<p>15:30 &#8212; 17:31 <b>Session 6<\/b><br \/>\nSession Chair: Gadi Taubenfeld (IDC Herzliya, Israel)<\/p>\n<ul>\n<li>15:30 &#8212; 15:53<br \/>\nSpace Bounds for Reliable Storage: Fundamental Limits of Coding<br \/>\nAlexander Spiegelman, Yuval Cassuto, Gregory Chockler and Idit Keidar<\/li>\n<li>15:53 &#8212; 16:16<br \/>\nSpecification and Complexity of Collaborative Text Editing<br \/>\nHagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang and Marek Zawirski<\/li>\n<li>16:16 &#8212; 16:39<br \/>\nOptimal Mobile Byzantine Fault Tolerant Distributed Storage<br \/>\nSilvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru and Sebastien Tixeuil<\/li>\n<li>16:39 &#8212; 17:02<br \/>\nA Markov Chain Algorithm for Compression in Self-Organizing Particle Systems<br \/>\nSarah Cannon, Josh Daymude, Dana Randall and Andrea Richa<\/li>\n<li>17:02 &#8212; 17:25<br \/>\nA Complexity-Based Hierarchy for Multiprocessor Synchronization<br \/>\nFaith Ellen, Rati Gelashvili, Nir Shavit and Leqi Zhu<\/li>\n<li>17:25 &#8212; 17:31<br \/>\nBrief Announcement: Asynchronous Coordination With Preferences and Constraints<br \/>\nArmando Casta\u00f1eda, Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum and Matthieu Roy<\/li>\n<li>17:31 &#8212; 17:37<br \/>\nBrief Announcement: A Key-Value Map for Massive Real-Time Analytics<br \/>\nDmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan Gueta, Eshcar Hillel, Moshe Sulamy and Idit Keidar<\/li>\n<\/ul>\n<p>18:00 &#8211; 21:00 <b>Banquet<\/b> (at\u00a0<a href=\"http:\/\/www.hotelpalomar-chicago.com\/downtown\/directions-map.html\">Hotel Palomar Chicago, <span class=\"street-address\">505 North State Street<\/span>, <span class=\"locality\">Chicago<\/span>, IL\u00a0<span class=\"postal-code\">60654<\/span>)<\/a><\/p>\n<h2>Thursday, July 28<\/h2>\n<p>8:40 &#8212; 9:40 <b>Keynote Lecture 3<\/b><\/p>\n<ul>\n<li><strong>How Emerging Memory Technologies Will Have You Rethinking <\/strong><strong>Algorithm Design<\/strong><br \/>\nPhillip B. Gibbons (Carnegie Mellon University)<\/li>\n<\/ul>\n<p>9:40 &#8212; 10:00 <b>Coffee break<\/b><\/p>\n<p>10:00 &#8212; 11:56 <b>Session 7<\/b><br \/>\nSession Chair: Yehuda Afek (Tel-Aviv University, Israel)<\/p>\n<ul>\n<li>10:00 &#8212; 10:23<br \/>\nInformation-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation<br \/>\nViveck Cadambe, Zhiying Wang and Nancy Lynch<\/li>\n<li>10:23 &#8212; 10:46<br \/>\nOn the Complexity of Reader-Writer Locks<br \/>\nDanny Hendler<\/li>\n<li>10:46 &#8212; 11:09<br \/>\nAn algorithm for replicated objects with efficient reads<br \/>\nTushar Chandra, Vassos Hadzilacos and Sam Toueg<\/li>\n<li>11:09 &#8212; 11:32<br \/>\nAre Shared Objects Composable under an Oblivious Adversary?<br \/>\nOksana Denysyuk and Philipp Woelfel<\/li>\n<li>11:32 &#8212; 11:38<br \/>\nBrief Announcement: A Family of Leaderless Generalized-Consensus Algorithms<br \/>\nGiuliano Losa, Sebastiano Peluso and Binoy Ravindran<\/li>\n<li>11:38 &#8212; 11:44<br \/>\nBrief Announcement: Computing in the Presence of Weak Crash Failures<br \/>\nGadi Taubenfeld<\/li>\n<li>11:44 &#8212; 11:50<br \/>\nBrief Announcement: Oh-RAM! One and a Half Round Read\/Write Atomic Memory<br \/>\nTheophanis Hadjistasi, Alexander Schwarzmann and Nicolas Nicolaou<\/li>\n<li>11:50 &#8212; 11:56<br \/>\nBrief Announcement: Space-Time Tradeoffs for Distributed Verification<br \/>\nMor Baruch, Rafail Ostrovsky and Will Rosenbaum<\/li>\n<\/ul>\n<p>12:00 &#8212; 13:30 <b>Lunch<\/b><\/p>\n<p>13:30 &#8212; 15:08 <b>Session 8<\/b><br \/>\nSession Chair: Marcos K. Aguilera (VMware Research Group, USA)<\/p>\n<ul>\n<li>13:30 &#8212; 13:53<br \/>\nA Faster Distributed Radio Broadcast Primitive (Extended Abstract)<br \/>\nBernhard Haeupler and\u00a0David Wajc<\/li>\n<li>13:53 &#8212; 14:16<br \/>\nBroadcast Extensions with Optimal Communication and Round Complexity<br \/>\nChaya Ganesh and Arpita Patra<\/li>\n<li>14:16 &#8212; 14:39<br \/>\nTwo-Bit Messages are Sufficient to Implement Atomic Read\/Write Registers in Crash-prone Systems<br \/>\nAchour Most\u00e9faoui and Michel Raynal<\/li>\n<li>14:39 &#8212; 15:02<br \/>\nHow proofs are prepared at Camelot<br \/>\nAndreas Bj\u00f6rklund and Petteri Kaski<\/li>\n<li>15:02 &#8212; 15:08<br \/>\nBrief Announcement: Proactive Secret Sharing with a Dishonest Majority<br \/>\nShlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky and Moti Yung<\/li>\n<\/ul>\n<p>15:10 &#8212; 15:30 <b>Coffee break<\/b><\/p>\n<p>15:30 &#8212; 17:03 <b>Session 9<\/b><br \/>\nSession Chair: Adrian Kosowski (LIAFA, Paris Diderot, France)<\/p>\n<ul>\n<li>15:30 &#8212; 15:53<br \/>\nSearch on a Line with Faulty Robots<br \/>\nJurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Jaroslav Opatrny<\/li>\n<li>15:53 &#8212; 16:16<br \/>\nUniform deployment of mobile agents in asynchronous rings<br \/>\nMasahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa and Toshimitsu Masuzawa<\/li>\n<li>16:16 &#8212; 16:39<br \/>\nFault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms<br \/>\nLili Su and Nitin Vaidya<\/li>\n<li>16:39 &#8211;16:45<br \/>\nBrief Announcement: Active Information Spread in Networks<br \/>\nGennaro Cordasco, Luisa Gargano, Adele Rescigno and Ugo Vaccaro<\/li>\n<li>16:45 &#8212; 16:51<br \/>\nBrief Announcement: Certified Universal Gathering in R2 for Oblivious Mobile Robots<br \/>\nPierre Courtieu, Lionel Rieg, Sebastien Tixeuil and Xavier Urbain<\/li>\n<li>15:51 &#8212; 16:57<br \/>\nBrief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation<br \/>\nQuentin Bramas and Sebastien Tixeuil<\/li>\n<li>16:57 &#8212; 17:03<br \/>\nBrief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space<br \/>\nYukiko Yamauchi, Taichi Uehara and Masafumi Yamashita<\/li>\n<\/ul>\n<p>17:15 &#8212; 18:42 <b>Session 10<\/b><br \/>\nSession Chair: Philipp Woelfel (University of Calgary, Canada)<\/p>\n<ul>\n<li>17:15 &#8212; 17:38<br \/>\nLow-Congestion Shortcuts without Embedding<br \/>\nBernhard Haeupler, Taisuke Izumi and Goran Zuzic<\/li>\n<li>17:38 &#8212; 18:01<br \/>\nThe coalescing-branching random walk on expanders and the dual epidemic process<br \/>\nColin Cooper, Tomasz Radzik and Nicolas Rivera<\/li>\n<li>18:01 &#8212; 18:24<br \/>\nAnt-Inspired Density Estimation via Random Walks<br \/>\nCameron Musco, Hsin-Hao Su and Nancy Lynch<\/li>\n<li>18:24 &#8212; 18:30<br \/>\nBrief Announcement: Multi-Broadcasting under the SINR Model<br \/>\nShailesh Vaya and Sai Praneeth Reddy K<\/li>\n<li>18:30 &#8212; 18:36<br \/>\nBrief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm<br \/>\nSriram Pemmaraju and Talal Riaz<\/li>\n<\/ul>\n<p>18:36 &#8212; 18:45 <b>Closing of PODC 2016<\/b><\/p>\n<h2>Friday, July 29<\/h2>\n<p>8:00 &#8212; 17:30 <b>Workshops<\/b><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Printable\u00a0Program\u00a0(pdf) UPDATED\u00a0Venue\u00a0Information Monday, July 25 8:00 &#8212; 17:30 Workshops 16:30 &#8212; 18:00 Faith Ellen Birthday Celebration 18:00 &#8212; 19:30 Reception Tuesday, July 26 8:30 &#8212; 8:40 Opening 8:40 &#8212; 9:40 Keynote Lecture 1 New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources Andrew A. Chien (The University of Chicago, Argonne National Laboratory) 9:40 &#8212; &hellip; <a href=\"https:\/\/www.podc.org\/podc2016\/program\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;PODC 2016 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-250","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/pages\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":27,"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/pages\/250\/revisions"}],"predecessor-version":[{"id":375,"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/pages\/250\/revisions\/375"}],"wp:attachment":[{"href":"https:\/\/www.podc.org\/podc2016\/wp-json\/wp\/v2\/media?parent=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}