8 papers
Error Term Estimates for Sets of Remainders
Omkar Baraskar, Prashant Gokhale, Sarvagya Jain +1
For a positive integer , let Baraskar and Vukusic proved for…
Asymptotic Behavior of Iterated Sets of Remainders
Omkar Baraskar, Prashant Gokhale, Sarvagya Jain +1
For a positive integer , let and put . The sets define…
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 eleme…
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…
Finding maximum matchings in RDV graphs efficiently
Therese Biedl, Prashant Gokhale
In this paper, we study the maximum matching problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. We show that this problem c…
Improved and Generalized Algorithms for Burning a Planar Point Set
Prashant Gokhale, J. Mark Keil, Debajyoti Mondal
Given a set of points in the plane, a point burning process is a discrete time process to burn all the points of where fires must be initiated at the given points. Specific…