On Differentially Private Linear Algebra
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916468680032256 |
|---|---|
| author | Kaplan, Haim Mansour, Yishay Moran, Shay Stemmer, Uri Tur, Nitzan |
| author_facet | Kaplan, Haim Mansour, Yishay Moran, Shay Stemmer, Uri Tur, Nitzan |
| contents | We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls. As an application, we obtain efficient DP algorithms for learning halfspaces and affine subspaces. Our algorithms addressing equalities are strongly polynomial, whereas those addressing inequalities are weakly polynomial. Furthermore, this distinction is inevitable: no DP algorithm for linear programming can be strongly polynomial-time efficient. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03087 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Differentially Private Linear Algebra Kaplan, Haim Mansour, Yishay Moran, Shay Stemmer, Uri Tur, Nitzan Data Structures and Algorithms We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls. As an application, we obtain efficient DP algorithms for learning halfspaces and affine subspaces. Our algorithms addressing equalities are strongly polynomial, whereas those addressing inequalities are weakly polynomial. Furthermore, this distinction is inevitable: no DP algorithm for linear programming can be strongly polynomial-time efficient. |
| title | On Differentially Private Linear Algebra |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.03087 |