Private approximation of NP-hard functions

DOI10.1145/380752.380850MaRDI QIDQ5176013zbMATH OpenOpenAlexFDO

Authors Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380850

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Cryptography (94A60)

Recommendations

• Private approximation of search problems
• Private Approximation of Search Problems
• Theory of Cryptography
• Private approximation of clustering and vertex cover
• Near-optimal private approximation protocols via a black box transformation

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(15)

• Private multiparty sampling and approximation of vector combinations
• How should we solve search problems privately?
• High-precision privacy-preserving real-valued function evaluation
• Functionally private approximations of negligibly-biased estimators
• Private approximation of search problems
• On the complexity of the minimum independent set partition problem
• Private Approximation of Clustering and Vertex Cover
• Private Approximation of Search Problems
• Brief announcement: Zero-knowledge protocols for search problems
• Two Party Distribution Testing: Communication and Security
• Fast Private Norm Estimation and Heavy Hitters
• scientific article; zbMATH DE number 2222198 (Why is no real title available?)
• Theory of Cryptography
• Private approximation of clustering and vertex cover
• On the privacy of sublinear-communication Jaccard index estimation via min-hash

This page was built for publication: Private approximation of NP-hard functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176013)