Cops, robbers, and threatening skeletons

DOI10.1145/2591796.2591849zbMath1315.05130OpenAlexW2098322943MaRDI QIDQ5259541

Ittai Abraham, Ofer Neiman, Anupam Gupta, Kunal Talwar, Cyril Gavoille

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://doi.org/10.1145/2591796.2591849

zbMATH Keywords

cops and robbersexcluded minorpadded decomposition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (12)

Metric decompositions of path-separable graphs ⋮ A tight lower bound for the capture time of the cops and robbers game ⋮ Unnamed Item ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Graph Clustering using Effective Resistance ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Unnamed Item ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs

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: Cops, robbers, and threatening skeletons