JGJeff Giliberti
Jeff Giliberti
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Jeff Giliberti has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Ali Vakilian
Department of Computer Science Virginia Tech 620 Drillfield Dr 24060 Blacksburg VA USA
1 shared publication - Jonas Sauer
Department of Informatics Karlsruhe Institute of Technology Am Fasanengarten 5 76131 Karlsruhe Germany
1 shared publication - Kiarash Banihashem
University of Maryland College Park MD USA
1 shared publication - MohammadTaghi Hajiaghayi
University of Maryland, College Park, USA
1 shared publication - Morteza Monemizadeh
Department of Mathematics and Computer Science TU Eindhoven The Netherlands
1 shared publication - Peyman Jabbarzade
University of Maryland College Park MD USA
1 shared publication
Latest Publications
- Open Access
Graph-Based Nearest-Neighbor Search without the Spread
$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.Open AccessGraph-Based Nearest-Neighbor Search without the Spread
$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$. - Open Access
Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \subset \mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary -- an adversary that, at any time $t$, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a worst-case update time of $\text{poly}(d, \log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+ε)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \cdot \text{poly}(ε^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot \text{poly}(ε^{-1}, \log n)$ by Biabani et al. [NeurIPS'24].Open AccessDynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \subset \mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary -- an adversary that, at any time $t$, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a worst-case update time of $\text{poly}(d, \log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+ε)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \cdot \text{poly}(ε^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot \text{poly}(ε^{-1}, \log n)$ by Biabani et al. [NeurIPS'24].