Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
- 講者Andrej Bogdanov 教授 (加拿大渥太華大學)
邀請人：鐘楷閔 - 時間2025-06-26 (Thu.) 10:15 ~ 12:15
- 地點資訊所新館101演講廳
摘要
In 1984 Johnson and Lindenstrauss showed that a random projection of an arbitrary point set S into low-dimensional space is approximately distance-preserving, as long as S is of size at most exponential in the target dimension. The resulting embedding has found many uses in data science.
If S is larger than exponential, however, its points can contract arbitrarily under the projection, opening the door to adversarial attacks.
We give evidence that when S is the n-dimensional hypergrid of integral points with bounded infinity-norm, the task of finding a contracting pair of points exhibits a computational-statistical gap. In a certain parameter range, contracting pairs are abundant, but finding such a pair is computationally infeasible.
As a cryptographic application, we show that the rounded Johnson-Lindenstrauss embedding is a robust property-preserving hash function. Such hash functions h compress data while preserving distances between inputs up to some distortion factor, with the guarantee that even knowing h, no computationally bounded adversary can find a pair of points that violates the distortion bound.
The talk is based on joint work with Alon Rosen, Neekon Vafa, and Vinod Vaikutanathan.
If S is larger than exponential, however, its points can contract arbitrarily under the projection, opening the door to adversarial attacks.
We give evidence that when S is the n-dimensional hypergrid of integral points with bounded infinity-norm, the task of finding a contracting pair of points exhibits a computational-statistical gap. In a certain parameter range, contracting pairs are abundant, but finding such a pair is computationally infeasible.
As a cryptographic application, we show that the rounded Johnson-Lindenstrauss embedding is a robust property-preserving hash function. Such hash functions h compress data while preserving distances between inputs up to some distortion factor, with the guarantee that even knowing h, no computationally bounded adversary can find a pair of points that violates the distortion bound.
The talk is based on joint work with Alon Rosen, Neekon Vafa, and Vinod Vaikutanathan.