29/05/2025
WHO: Prof. Shay Moran, Technion
WHEN: Thursday, May 29th 2025 at 12:00
WHERE: BUILDING 503 (Computer Science) AUDITORIUM
Affiliation:
Departments of Mathematics, Computer Science, and Data & Decision Sciences at the Technion, and Google Research Tel Aviv.
Title:
Differential Privacy Meets Linear Algebra: Algorithms, Limits, and Applications
Abstract:
Differential privacy (DP) has emerged as a powerful framework for designing algorithms that protect sensitive data. In this talk, I will present a line of work that explores the intersection of differential privacy and linear algebra, introducing efficient DP algorithms for fundamental algebraic tasks: solving systems of linear equations over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls.
Our algorithms for solving equalities are strongly polynomial, while those for inequalities are only weakly polynomial—and this gap is provably inherent. As an application of these techniques, we obtain new efficient DP algorithms for learning halfspaces and affine subspaces, tasks central to modern machine learning.
Short Bio:
Shay Moran is a faculty member at the Technion, holding positions in the Departments of Mathematics, Computer Science, and Data & Decision Sciences, and is also affiliated with Google Research. His work focuses on the theoretical foundations of machine learning, with contributions spanning learning theory, differential privacy, computational geometry, and combinatorics. Shay’s research has resolved several long-standing open problems and has been recognized with prestigious awards, including Best Paper Awards at FOCS and COLT, as well as an ERC grant. He is particularly interested in uncovering connections between machine learning and diverse areas of mathematics, and in fostering interdisciplinary collaboration.
