261 citations · 836 across the 30 of their papers we have counts for
5 papers · 1 filter
Adversarial Examples from Cryptographic Pseudo-Random Generators
Sébastien Bubeck, Yin Tat Lee, Eric Price +1
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the…
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev +1
We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a…
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
Consider an instance of Euclidean -means or -medians clustering. We show that the cost of the optimal solution is preserved up to a factor of under a projec…
Approximate Nearest Neighbor Search in High Dimensions
Alexandr Andoni, Piotr Indyk, Ilya Razenshteyn
The nearest neighbor problem is defined as follows: Given a set of points in some metric space , build a data structure that, given any point , returns a point in…
Adversarial examples from computational constraints
Sébastien Bubeck, Eric Price, Ilya Razenshteyn
Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due…