4 papers
Dynamic estimation of slowly varying sequences
Prashant Gokhale, Mikhail Khodak, Sandeep Silwal
We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude of the difference between the elem…
Compact Geometric Representations of Hierarchies
Prashant Gokhale, Piotr Indyk, Yuhao Liu +3
Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared…
Adversarially Robust Approximate Furthest Neighbor
Kiarash Banihashem, Jeff Giliberti, Prashant Gokhale +5
We work in the adaptive query model, where one is given a point set and seeks to construct a data structure that can answer correctly and efficiently a seq…
Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
Therese Biedl, Prashant Gokhale
In this paper, we study the dominating set problem in \emph{RDV graphs}, a graph class that lies between interval graphs and chordal graphs and is defined as the \textbf{v}ertex-in…