VLDB 2026 Research / reviewers in the wild / expert
Elie Abboud
dblp:348/5920
· DBLP profile ↗
3ranked-venue papers
2as first author
3since 2021 · last 2025
0009-0005-9611-9608ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 first-author · 2 since 2021Artificial intelligence and machine learning · 1 · 1 since 2021Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | Finer-grained reductions in fine-grained hardness of approximation
Elie Abboud, Noga Ron-Zewi |
Theor. Comput. Sci. | 1 |
| 2024 | Finer-Grained Reductions in Fine-Grained Hardness of ApproximationabstractWe investigate the relation between $δ$ and $ε$ required for obtaining a $(1+δ)$-approximation in time $N^{2-ε}$ for closest pair problems under various distance metrics, and for other related problems in fine-grained complexity. Specifically, our main result shows that if it is impossible to (exactly) solve the (bichromatic) inner product (IP) problem for vectors of dimension $c \log N$ in time $N^{2-ε}$, then there is no $(1+δ)$-approximation algorithm for (bichromatic) Euclidean Closest Pair running in time $N^{2-2ε}$, where $δ\approx (ε/c)^2$ (where $\approx$ hides $\polylog$ factors). This improves on the prior result due to Chen and Williams (SODA 2019) which gave a smaller polynomial dependence of $δ$ on $ε$, on the order of $δ\approx (ε/c)^6$. Our result implies in turn that no $(1+δ)$-approximation algorithm exists for Euclidean closest pair for $δ\approx ε^4$, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of $δ\approx ε^3$ for Euclidean closest pair, given by the best known algorithm of Almam, Chan, and Williams (FOCS 2016). By known reductions, a similar result follows for a host of other related problems in fine-grained hardness of approximation. Our reduction combines the hardness of approximation framework of Chen and Williams, together with an MA communication protocol for IP over a small alphabet, that is inspired by the MA protocol of Chen (Theory of Computing, 2020). Elie Abboud, Noga Ron-Zewi |
ICALP | 1 |
| 2023 | MFSC: Matching by Few-Shot Classification
Daniel Shalam, Elie Abboud, Roee Litman, Simon Korman |
BMVC | 2 |