A polynomial-time differentially private algorithm approximates every cut in a graph within (1+γ) multiplicative and n^{1.25+o(1)} additive error, breaking the previous n^{1.5} barrier.
Stop the Open Data Bus, We Want to Get Off
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The subject of this report is the re-identification of individuals in the Myki public transport dataset released as part of the Melbourne Datathon 2018. We demonstrate the ease with which we were able to re-identify ourselves, our co-travellers, and complete strangers; our analysis raises concerns about the nature and granularity of the data released, in particular the ability to identify vulnerable or sensitive groups.
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
A polynomial-time differentially private algorithm approximates every cut in a graph within (1+γ) multiplicative and n^{1.25+o(1)} additive error, breaking the previous n^{1.5} barrier.