SPAA 2016: 28TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES
PROGRAM

Days: Monday, July 11th Tuesday, July 12th Wednesday, July 13th

Monday, July 11th

View this program: with abstractssession overviewtalk overview

09:00-10:20 Session 1: Parallel Algorithms
09:00
Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation) ( abstract )
09:20
Parallel Algorithms for Summing Floating-Point Numbers ( abstract )
09:40
Randomized approximate nearest neighbor search with limited adaptivity ( abstract )
10:00
Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications ( abstract )
13:30-15:00 Session 3: Scheduling Parallel Computation
13:30
Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers ( abstract )
13:50
A Practical Solution to the Cactus Stack problem ( abstract )
14:10
Latency-Hiding Work Stealing ( abstract )
14:30
Provably good and practically efficient parallel race detection for fork-join programs ( abstract )
14:50
Dynamic Determinacy Race Detection for Task Parallelism with Futures ( abstract )
15:30-16:40 Session 4: Transactional Memory and Beyond
15:30
RUBIC: Online Parallelism Tuning for Collocated Transactional Memory Applications ( abstract )
15:50
Extending TM Primitives using Low Level Semantics ( abstract )
16:10
Investigating the performance of hardware transactions on a multi-socket machine ( abstract )
16:30
Brief Announcement: Transactional Data Structure Libraries ( abstract )
17:00-18:00 Session 5: Parallel Algorithms
Chair:
17:00
Cache-Adaptive Analysis ( abstract )
17:20
Parallel Algorithms for Asymmetric Read-Write Costs ( abstract )
17:40
Brief Announcement: Preserving Happens-before in Persistent Memory ( abstract )
17:50
Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling ( abstract )
Tuesday, July 12th

View this program: with abstractssession overviewtalk overview

09:00-10:30 Session 6: Scheduling
09:00
General Profit Scheduling and the Power of Migration on Heterogeneous Machines ( abstract )
09:20
The Power of Migration in Online Machine Minimization ( abstract )
09:40
Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines ( abstract )
10:00
Scheduling Parallelizable Jobs Online to Minimize Maximum Flow Time ( abstract )
10:20
A QPTAS for Non-preemptive Speed-scaling ( abstract )
13:30-15:00 Session 8: Scheduling and Resource Allocation
13:30
Robust and Probabilistic Failure-Aware Placement ( abstract )
13:50
Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks ( abstract )
14:00
Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time ( abstract )
14:20
Improved Approximation Algorithms for Scheduling Co-Flows ( abstract )
14:30
Parallelism in Randomized Incremental Algorithms ( abstract )
14:50
Energy optimization of memory intensive parallel workloads ( abstract )
15:30-16:40 Session 9: Parallel Algorithms
15:30
Just Join for Parallel Ordered Sets and Maps ( abstract )
15:50
Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis ( abstract )
16:10
Parallel Approaches to the String Matching Problem on the GPU ( abstract )
16:30
Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs ( abstract )
17:00-18:00 Session 10: Robots, Amoebots, and Cobras (Oh my!)
17:00
Universal Shape Formation for Programmable Matter ( abstract )
17:20
Asymptotically Optimal Gathering on a Grid ( abstract )
17:40
Better bounds for coalescing-branching random walks on graphs ( abstract )
Wednesday, July 13th

View this program: with abstractssession overviewtalk overview

09:00-10:20 Session 11: Concurrent Data Structures
Chair:
09:00
Lock-free Transactions without Aborts for Linked Data Structures ( abstract )
09:20
Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free ( abstract )
09:40
Fast and Robust Memory Reclamation for Concurrent Data Structures ( abstract )
10:00
Benchmarking Concurrent Priority Queues: Performance of k-LSM and Related Data Structures ( abstract )
10:10
Fast Concurrent Cuckoo Kick-out Eviction Schemes for High-Density Tables ( abstract )
10:40-12:00 Session 12: Graph Algorithms
10:40
The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets ( abstract )
11:00
Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph? ( abstract )
11:20
Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures ( abstract )
11:40
Applications of Uniform Sampling: Densest Subgraph and Beyond ( abstract )
11:50
Brief Announcement: Relaxed Byzantine Vector Consensus ( abstract )
13:30-14:40 Session 13: Distributed Algorithms
13:30
The Cost of Unknown Diameter in Dynamic Networks ( abstract )
13:50
Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration ( abstract )
14:10
Fast Distributed Algorithms for Connectivity and MST in Large Graphs ( abstract )
14:30
A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications ( abstract )
15:00-16:00 Session 14: Parallel Graph Algorithms
15:00
Parallel Shortest-Paths Using Radius Stepping ( abstract )
15:20
Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford ( abstract )
15:40
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches ( abstract )