Many methods in differentially private model training rely on computing the similarity
between a query point (such as public or synthetic data) and private data. We abstract out …

Vehicles equipped with various sensing devices have the strong ability to generate location
information, which is beneficial to a lot of applications in smart city. In special, it is important …

In this paper, we scale evolutionary algorithms to high-dimensional optimization problems
that deceptively possess a low effective dimensionality (certain dimensions do not …

We study the effect of Johnson-Lindenstrauss transforms in various projective clustering
problems, generalizing results which only applied to center-based clustering [40]. We ask …

The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via
a random linear map, which has become a fundamental technique in many computational …

Abstract The Johnson-Lindenstrauss family of transforms constitutes a key algorithmic tool
for reducing the dimensionality of a Euclidean space with low distortion of distances …

Cryptographic primitives have been used for various non-cryptographic objectives, such as
eliminating or reducing randomness and interaction. We show how to use cryptography to …

We propose a new" bi-metric" framework for designing nearest neighbor data structures. Our
framework assumes two dissimilarity functions: a ground-truth metric that is accurate but …

Oblivious dimension reduction,\{a} la the Johnson-Lindenstrauss (JL) Lemma, is a
fundamental approach for processing high-dimensional data. We study this approach for …

A key cog in machine learning is the humble embedding: vector representations of real
world objects such as text, images, graphs, or molecules whose geometric similarities …