Private approximation of NP-hard functions

DOI10.1145/380752.380850zbMath1323.68569OpenAlexW2035825137MaRDI QIDQ5176013

Eyal Kushilevitz, Shai Halevi, Robert Krauthgamer, 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

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

Related Items (5)

Unnamed Item ⋮ How should we solve search problems privately? ⋮ Fast Private Norm Estimation and Heavy Hitters ⋮ Private multiparty sampling and approximation of vector combinations ⋮ Two Party Distribution Testing: Communication and Security

Cites Work

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

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