Parallel algorithms for geometric graph problems

DOI10.1145/2591796.2591805zbMath1315.05133arXiv1401.0042OpenAlexW2057082426MaRDI QIDQ5259593

Alexandr Andoni, Grigory Yaroslavtsev, Aleksandar Nikolov, Krzysztof Onak

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.0042

zbMATH Keywords

parallel computationminimum spanning treeMapReduceearth-mover distance

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (17)

Equivalence classes and conditional hardness in massively parallel computations ⋮ FPTAS for minimizing the earth mover's distance under rigid transformations and related problems ⋮ Deterministic Massively Parallel Connectivity ⋮ Component stability in low-space massively parallel computation ⋮ Maliciously secure massively parallel computation for all-but-one corruptions ⋮ Unnamed Item ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ Round Compression for Parallel Matching Algorithms ⋮ Brief Announcement: MapReduce Algorithms for Massive Trees ⋮ On Geometric Prototype and Applications ⋮ Preconditioning for the Geometric Transportation Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A unified framework for clustering constrained data without locality property ⋮ Neighborhood hypergraph model for topological data analysis ⋮ Distributed algorithms for matching in hypergraphs

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Parallel algorithms for geometric graph problems