SPAA 2019 Conference Program

The SPAA 2019 program is now available.


SPAA 2019 Accepted Papers

Regular Papers (in no particular order):

Michael Elkin and Ofer Neiman. Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC
Leszek Gasieniec, Grzegorz Stachowiak and Przemysław Uznański. Almost logarithmic-time space optimal leader election in population protocols
Mosharaf Chowdhury, Samir Khuller, Manish Purohit, Sheng Yang and Jie You. Near Optimal Coflow Scheduling in Networks
Yossi Azar, Yuval Emek, Rob van Stee and Danny Vainstein. The Price of Clustering in Bin-Packing with Applications to Bin-Packing with Delays
Pankaj Khanchandani and Roger Wattenhofer. The Arvy Distributed Directory Protocol
Andrzej Pelc and Ram Narayan Yadav. Using Time to Break Symmetry: Universal Deterministic Anonymous Rendezvous
Emmanuelle Anceaume, Antonella Del Pozzo, Romaric Ludinard, Maria Potop-Butucaru and Sara Tucci-Piergiovanni. Blockchain Abstract Data Type
Vipul Harsh, Laxmikant Kale and Edgar Solomonik. Histogram Sort with Sampling
Naama Ben-David, Guy Blelloch, Yihan Sun and Yuanhao Wei. Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
Haimin Chen and Chaodong Zheng. Fast and Resource Competitive Broadcast in Multi-channel Radio Networks
Naama Ben-David, Guy Blelloch, Michal Friedman and Yuanhao Wei. Dely-Free Concurrency on Faulty Persistent Memory
Gal Beniamini and Oded Schwartz. Faster Matrix Multiplication via Sparse Decomposition
Diego Didona, Panagiota Fatourou, Rachid Guerraoui, Jingjing Wang and Willy Zwaenepoel. Distributed Transactional Systems Cannot Be Fast
Bogdan Chlebus, Elijah Hradovich, Tomasz Jurdzinski, Marek Klonowski and Dariusz Kowalski. Energy Efficient Adversarial Routing in Shared Channels
Jiwon Choe, Amy Huang, Tali Moreshet, Maurice Herlihy and R. Iris Bahar. Concurrent Data Structures with Near-Data-Processing: An Architecture-Aware Implementation
Kilian Grage, Klaus Jansen and Kim-Manuel Klein. An EPTAS for machine scheduling with bag-constraints.
Michael Feldmann and Christian Scheideler. Skeap & Seap: Scalable Distributed Priority Queues for constant and arbitrary Priorities
Faith Ellen, Barun Gorain, Avery Miller and Andrzej Pelc. Constant-Length Labeling Schemes for Deterministic Radio Broadcast
John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li and Christian Scheideler. Distributed Computation in Node-Capacitated Networks
Umut Acar, Daniel Anderson, Guy Blelloch and Laxman Dhulipala. Parallel Batch-Dynamic Graph Connectivity
Panagiota Fatourou, Elias Papavasileiou and Eric Ruppert. Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries
Omar Obeya, Endrias Kahssay, Edward Fan and Julian Shun. Theoretically-Efficient and Practical Parallel In-Place Radix Sorting
Davide Bilò, Tobias Friedrich, Pascal Lenzner and Anna Melnichenko. Geometric Network Creation Games
Max A. Deppert and Klaus Jansen. Near-Linear Approximation Algorithms for Scheduling Problems with Batch Setup Times
Dan Alistarh, Giorgi Nadiradze and Nikita Koval. Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers
Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni and Nikos Parotsidis. Dynamic Algorithms for the Massively Parallel Computation Model
Christoph Lenzen, Merav Parter and Eylon Yogev. Parallel Balanced Allocations: The Heavily Loaded Case
Nicolas Rivera, Thomas Sauerwald, Alexandre Stauffer and John Sylvester. The dispersion time of random walks on finite graphs (regular paper)
Mahdi Boroujeni and Saeed Seddighin. Improved MPC Algorithms for Edit Distance and Ulam Distance
David Eppstein and Vijay Vazirani. NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs
Nan Kang and Nicolas Rivera. Best-of-Three Voting in Dense Graphs
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni and Warren Schudy. Massively Parallel Computation via Remote Memory Access
Rathish Das, Shih-Yu Tsai, Sharmila Duppala, Jayson Lynch, Esther Arkin, Rezaul Chowdhury, Joseph Mitchell and Steven Skiena. Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
Michael A. Bender, Alexander Conway, Martin Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara McAllister, Nirjhar Mukherjee, Prashant Pandey, Donald E. Porter, Jun Yuan and Yang Zhan. The Dictionary Problem, Optimal Searching, and Asymptotic Distortions of the DAM Model

Brief Announcements (in no particular order):

William Wang and Stephan Diestelhorst. Brief Announcement: Persistent Atomics for Implementing Durable Lock-Free Data Structures for Non-Volatile Memory
Ali Pourmiri and Fahimeh Ramezani. Brief Announcement: Ultra-Fast Asynchronous Randomized Rumor Spreading
Nathan Beckmann, Phillip B. Gibbons, Bernhard Haeupler and Charles McGuffey. Brief Announcement: Writeback Aware Caching
Rohan Yadav and Umut Acar. Brief Announcement: Work Efficient Parallel Graph Isomorphism
Chenglong Li, Tao Li, Junnan Li, Hui Yang and Baosheng Wang. Brief Announcement: A Memory Optimized Architecture for Multi-Field Packet Classification
Alessandro Epasto, Vahab Mirrokni and Morteza Zadimoghaddam. Brief Announcement: Scalable diversity maximization via small-size composable core-sets
Lin Chen, Minming Li, Guohui Lin and Kai Wang. Brief Announcement: Approximation of Scheduling with Calibrations on Multiple Machines
Kristian Hinnenthal, Christian Scheideler and Martijn Struijs. Brief Announcement: Fast Distributed Algorithms for LP-Type Problems of Bounded Dimension
Kyle Singer, Kunal Agrawal and I-Ting Angelina Lee. Brief Announcement: Reduced I/O Latency with Futures
Tingzhe Zhou, Pantea Zardoshti and Michael Spear. Brief Announcement: Optimizing Persistent Transactions
Tal Wagner. Brief Announcement: Eccentricity Heuristics through Sublinear Analysis Lenses