|  |
||||||||||
Table of Contents Foreword |
|||||||||||
| |
|||||||||||
| KEYNOTE
LECTURE 1 Beyond
P vs. NP: Quadratic-Time Hardness for Big Data Problems (Page
1) |
|||||||||||
| SESSION
1 Randomized
Composable Coresets for Matching and Vertex Cover (Page
3) Almost
Optimal Streaming Algorithms for Coverage Problems (Page
13) Bicriteria
Distributed Submodular Maximization in a Few Rounds (Page
25) On
Energy Conservation in Data Centers (Page
35) |
|||||||||||
| SESSION
2 Asymptotically
Optimal Approximation Algorithms for Coflow Scheduling (Page
45) Online
Flexible Job Scheduling for Minimum Span (Page
55) Minimizing
Total Weighted Flow Time with Calibrations (Page
67) Tight
Bounds for Clairvoyant Dynamic Bin Packing (Page
77) Brief
Announcement: Scheduling Parallelizable Jobs Online to Maximize Throughput (Page
87) Brief
Announcement: A New Improved Bound for Coflow Scheduling (Page
91) |
|||||||||||
| SESSION
3 Bounding
Laconic Proof Systems by Solving CSPs in Parallel (Page
95) Matrix
Multiplication, a Little Faster (Page
101) A
Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue
Problem (Page 111) Sharing
is Caring: Multiprocessor Scheduling with a Sharable Resource (Page
123) Brief
Announcement: Graph Matching in Massive Datasets (Page
133) Brief
Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for
Set Intersection Queries and Sparse Boolean Matrix Multiplication (Page
137) |
|||||||||||
| KEYNOTE
LECTURE 2 Some
Sequential Algorithms are Almost Always Parallel (Page
141) |
|||||||||||
| SESSION
4 Distributed
Partial Clustering (Page
143) Distributed
Detection of Cycles (Page
153) Distributed
Graph Clustering by Load Balancing (Page
163) Fast
Scheduling in Distributed Transactional Memory (Page
173) |
|||||||||||
| SESSION
5 Is
Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions (Page
183) Optimal
Reissue Policies for Reducing Tail Latency (Page
195) Impact
of Knowledge on Election Time in Anonymous Networks (Page
207) Swarm-based
Incast Congestion Control in Datacenters Serving Web Applications (Page
217) Brief
Announcement: Approximation Algorithms for Unsplittable Resource Allocation
Problems with Diseconomies of Scale (Page
227) Brief
Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource
Allocation (Page
231) |
|||||||||||
| SESSION
6 Concurrent
Data Structures for Near-Memory Computing (Page
235) Lower
Bounds in the Asymmetric External Memory Model (Page
247) Hand-Over-Hand
Transactions with Precise Memory Reclamation (Page
255) Optimal
Local Buffer Management for Information Gathering with Adversarial Traffic (Page
265) Brief
Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation (Page
275) Brief
Announcement: STAR (Space-Time Adaptive and Reductive) Algorithms for
Dynamic Programming Recurrences with more than O(1) Dependency (Page
279) |
|||||||||||
| SESSION
7 Near
Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs (Page
283) Julienne:
A Framework for Parallel Graph Algorithms using Work-efficient Bucketing (Page
293) Improved
Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs (Page
305) The
Mobile Server Problem (Page
313) Brief
Announcement: Efficient Best Response Computation for Strategic Network
Formation under Attack (Page
321) Brief
Announcement: Complete Visibility for Oblivious Robots in Linear Time (Page
325) |
|||||||||||
| SESSION
8 Online
Tree Caching (Page
329) Provably
Efficient Scheduling of Cache-oblivious Wavefront Algorithms (Page
339) Bounding
Cache Miss Costs of Multithreaded Computations Under General Schedulers (Page
351) Brief
Announcement: Meeting the Challenges of Parallelizing Sequential Programs (Page
363) Brief
Announcement: Hazard Eras - Non-Blocking Memory Reclamation (Page
367) Brief
Announcement: Extending Transactional Memory with Atomic Deferral (Page
371) Brief
Announcement: Hardware Transactional Storage Class Memory (Page
375) |
|||||||||||