Private Approximation of Search Problems

DOI10.1137/060671899MaRDI QIDQ3642862zbMATH OpenOpenAlexFDO

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

Publication date 6 November 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060671899

zbMATH Keywords

vertex coversecure computationprivate approximationsolution-list algorithms

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?
• scientific article; zbMATH DE number 7164746 (Why is no real title available?)
• Two Party Distribution Testing: Communication and Security
• Private approximation of search problems
• Theory of Cryptography
• Functionally private approximations of negligibly-biased estimators
• Private Approximation of Clustering and Vertex Cover
• Differentially private combinatorial optimization
• 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?)
• 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 Q3642862)