Private approximation of search problems

DOI10.1145/1132516.1132533MaRDI QIDQ2931376zbMATH OpenOpenAlexFDO

Authors Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

Publication date 25 November 2014

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

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

zbMATH Keywords

vertex coversecure computationprivate approximationsolution-list algorithm

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Private Approximation of Search Problems
• Private approximation of NP-hard functions
• The Asymptotic Capacity of Private Search
• Theory of Cryptography
• scientific article; zbMATH DE number 2090941
• Near-optimal private approximation protocols via a black box transformation
• Privately solving linear programs
• Differentially private combinatorial optimization
• Privacy-preserving linear and nonlinear approximation via linear programming
• Private approximation of clustering and vertex cover

Cited in

(13)

• How Should We Solve Search Problems Privately?
• Functionally private approximations of negligibly-biased estimators
• Private Approximation of Clustering and Vertex Cover
• Private Approximation of Search Problems
• Fast Private Norm Estimation and Heavy Hitters
• Differentially private combinatorial optimization
• Private multiparty sampling and approximation of vector combinations
• How should we solve search problems privately?
• Private approximation of NP-hard functions
• Private approximation of clustering and vertex cover
• scientific article; zbMATH DE number 975414 (Why is no real title available?)
• Brief announcement: Zero-knowledge protocols for search problems
• scientific article; zbMATH DE number 2222198 (Why is no real title available?)

This page was built for publication: Private approximation of search problems

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