# Ameya Velingker

### Research Areas

Authored Publications

Google Publications

Other Publications

Sort By

Efficient Location Sampling Algorithms for Road Networks

Sreenivas Gollapudi

Vivek Kumar

Santhoshini Velusamy

WebConf (2024)

Preview abstract
Many geographic information systems applications rely on the data provided by user devices in the road network. Such applications include traffic monitoring, driving navigation, detecting road closures or the construction of new roads, etc. This signal is collected by sampling locations from the user trajectories and is a critical process for all such systems. Yet, it has not been sufficiently studied in the literature. The most natural way to sample a trajectory is perhaps using a frequency based algorithm, e.g., sample every $x$ seconds. However, as we argue in this paper, such a simple strategy can be very wasteful in terms of resources (e.g., server-side processing, user battery) and in terms of the amount of user data that it maintains. In this work we conduct a horizontal study of various location sampling algorithms (including frequency-based, road geography-based, reservoir-sampling based, etc.) and extract their trade-offs in terms of various metrics of interest, such as, the size of the stored data and the induced quality of training for prediction tasks (e.g., predicting speeds) using the road network of New York City.
View details

Private Aggregation from Fewer Anonymous Messages

Rasmus Pagh

Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2020), pp. 798-827

Preview abstract
Consider the setup where n parties are each given a number x_i in F_q and the goal is to compute the sum of x_i in a secure fashion and with as little communication as possible. We study this problem in
the anonymized model of Ishai et al. (FOCS 2006) where each party may broadcast anonymous messages on an insecure channel.
We present a new analysis of the one-round "split and mix" protocol of Ishai et al. In order to achieve the same security parameter, our analysis reduces the required number of messages by a Θ(log n) multiplicative factor. We complement our positive result with lower bounds showing that the dependence of the number of messages on the domain size, the number of parties, and the security parameter is essentially tight.
Using a reduction of Balle et al. (2019), our improved analysis of the protocol of Ishai et al. yields, in the same model, an (ε, δ)-differentially private protocol for aggregation that, for any constant ε > 0 and any δ = 1 / poly(n), incurs only a constant error and requires only a constant number of messages per party. Previously, such a protocol was known only for Θ(log n) messages per party.
View details

Oblivious Sketching of High-Degree Polynomial Kernels

Thomas D. Ahle

Michael Kapralov

Jakob B. T. Knudsen

Rasmus Pagh

David P. Woodruff

Amir Zandieh

SODA (Symposium on Discrete Algorithms) (2020), pp. 141-160

Preview abstract
Kernel methods are fundamental tools in machine learning that allow detection of non-linear
dependencies between data without explicitly constructing feature vectors in high dimensional
spaces. A major disadvantage of kernel methods is their poor scalability: primitives such as
kernel PCA or kernel ridge regression generally take prohibitively large quadratic space and (at
least) quadratic time, as kernel matrices are usually dense. Some methods for speeding up kernel
linear algebra are known, but they all invariably take time exponential in either the dimension
of the input point set (e.g., fast multipole methods suffer from the curse of dimensionality) or
in the degree of the kernel function.
Oblivious sketching has emerged as a powerful approach to speeding up numerical linear
algebra over the past decade, but our understanding of oblivious sketching solutions for kernel
matrices has remained quite limited, suffering from the aforementioned exponential dependence
on input parameters. Our main contribution is a general method for applying sketching solutions
developed in numerical linear algebra over the past decade to a tensoring of data points without
forming the tensoring explicitly. This leads to the first oblivious sketch for the polynomial
kernel with a target dimension that is only polynomially dependent on the degree of the kernel
function, as well as the first oblivious sketch for the Gaussian kernel on bounded datasets that
does not suffer from an exponential dependence on the dimensionality of input data points.
View details

Pure Differentially Private Summation from Anonymous Messages

Noah Golowich

Ravi Kumar

Rasmus Pagh

Information Theoretic Cryptography (ITC) (2020), 15:1-15:23

Preview abstract
The shuffled (aka anonymous) model has recently generated significant interest as a candidate dis- tributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically:
• For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-
differentially private protocol for estimating the number of ones held by the users up to an absolute
error of Oε(1), and where each user sends Oε(logn) messages each consisting of a single bit. This √
is the first pure differentially private protocol in the shuffled model with error o( n) for constant values of ε.
Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers (in [0,1]) up to an absolute error of Oε(1), and where each user sends Oε(log3 n) messages each consisting of O(loglogn) bits.
• In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n0.5−Ω(1), the per user communication has to be at least
Ωε( log n) bits. This implies (i) the first separation between the (bounded-communication) multi- message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model.
Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question which might be of independent interest: given γ ∈ (0, 1), what is the smallest positive integer m for which there exist two random variables X0 and X1 supported on {0, . . . , m} such that (i) the total variation distance between X0 and X1 is at least 1 − γ, and (ii) the moment generating functions of X0 and X1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Θ(
View details

No Results Found