Ahmed Abdelkader
I obtained my PhD in Computer Science from the University of Maryland at College Park, where I wrote a thesis on geometric approximations and was lucky to have David Mount as my advisor. During my PhD, I spent a lot of time at Sandia National Labs working on meshing algorithms with Scott Mitchell and Mohamed Ebeida. Before leaving Maryland, I did a few projects on adversarial robustness in collaboration with Tom Goldstein's group. Prior to all that, I studied computer engineering and TA’ed many math/CS undergrad classes at Alexandria University in Egypt.
Authored Publications
Sort By
Differentiable Approximations for Distance Queries
David M. Mount
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Preview abstract
The widespread use of gradient-based optimization has motivated the adaptation of various classical algorithms into differentiable solvers compatible with learning pipelines. In this paper, we investigate the enhancement of traditional geometric query problems such that the result consists of both the geometric function as well as its gradient. Specifically, we study the fundamental problem of distance queries against a set of points P in R^d, which also underlies various similarity measures for learning algorithms.
The main result of this paper is a multiplicative (1+epsilon)-approximation of the Euclidean distance to P which is differentiable at all points in R^d \ P with asymptotically optimal bounds on the norms of its gradient and Hessian, from a data structure with storage and query time matching state-of-the-art results for approximate nearest-neighbor searching. The approximation is realized as a regularized distance through a partition-of-unity framework, which efficiently blends multiple local approximations, over a suitably defined covering of space, into a smooth global approximation. In order to obtain the local distance approximations in a manner that facilitates blending, we develop a new approximate Voronoi diagram based on a simple point-location data structure, simplifying away both the lifting transformation and ray shooting.
View details
