Shay Moran: "Differentially Private Linear Algebra" скачать в хорошем качестве

Shay Moran: "Differentially Private Linear Algebra"

Differential privacy (DP) has emerged as a powerful framework for designing algorithms that protect sensitive data. In this talk, I will present our work at the intersection of differential privacy and linear algebra, introducing efficient DP algorithms for fundamental algebraic tasks: solving systems of linear equations over arbitrary fields, solving linear inequalities over the reals, and computing affine spans and convex hulls.Our algorithms for equalities are strongly polynomial, while those for inequalities are only weakly polynomial—and this gap is provably inherent. As applications, we obtain the first efficient DP algorithms for learning halfspaces and affine subspaces. The talk will not assume prior familiarity with differential privacy; I will begin with a review of the definition.