Peyman Afshani

Peyman Afshani

Auto-generated profile, based on publicly available information

Peyman Afshani

Department of Computer Science Aarhus University Denmark

Research Focus & Metrics

Academic Career Length

16Years (2011-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2013
Verified
Book Chapter
Closed access
PDF file
PAPeyman Afshani
Peyman Afshani
MAManindra Agrawal
Manindra Agrawal
BDBenjamin Doerr
Benjamin Doerr
CDCarola Doerr
Carola Doerr
KLKasper Green Larsen
Kasper Green Larsen
KMKurt Mehlhorn
Kurt Mehlhorn

21 March 2011
Verified
Conference Paper
Open access
PDF file
PAPeyman Afshani
Peyman Afshani
PAPankaj K. Agarwal
Pankaj K. Agarwal
LALars Arge
Lars Arge
KLKasper Green Larsen
Kasper Green Larsen
JPJeff M. Phillips
Jeff M. Phillips
Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each point's uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline.

18 April 2023 in Journal of the ACM
Verified
Journal Article
Open access
PAPeyman Afshani
Peyman Afshani
PCPingan Cheng
Pingan Cheng
In the semialgebraic range searching problem, we are given a set of n points in ℝ d , and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, the problem is well-understood: It can be solved using S(n) space and with Q(n) query time with \(S(n)Q(n)^d = \tilde{O}(n^d),\) where the \(\tilde{O}(\cdot)\) notation hides polylogarithmic factors and this trade-off is tight (up to n o (1) factors). In particular, there exist “low space” structures that use O(n) space with O ( n 1-1/ d } ) query time [ 8 , 25 ] and “fast query” structures that use O ( n d ) space with O (log n ) query time [ 9 ]. However, for general semialgebraic ranges, only “low space” solutions are known, but the best solutions [ 7 ] match the same trade-off curve as simplex queries, with O ( n ) space and \(\tilde{O}(n^{1-1/d})\) query time. It has been conjectured that the same could be done for the “fast query” case, but this open problem has stayed unresolved. Here, we disprove this conjecture. We give the first nontrivial lower bounds for semialgebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting, with Q ( n ) query time must use \(S(n)=\overset{\scriptscriptstyle o}{\Omega }(n^3/Q(n)^5)\) space, where the \(\overset{\scriptscriptstyle o}{\Omega }(\cdot)\) notation hides \(n^{o(1)}\) factors, meaning, for \(Q(n)=\log ^{O(1)}n\) , \(\overset{\scriptscriptstyle o}{\Omega }(n^3)\) space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by \(\lbrace (x,y)\in \mathbb {R}^2:P(x)\le y\le P(x)+w\rbrace\) , where \(P(x)=\sum _{i=0}^\Delta a_i x^i\) is a univariate polynomial of degree Δ and \(a_0, \ldots , a_\Delta , w\) are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of \(\overset{\scriptscriptstyle o}{\Omega }(n^{\Delta +1}/Q(n)^{(\Delta +3)\Delta /2})\) , which implies that for \(Q(n)=\log ^{O(1)}n\) , we must use \(\overset{\scriptscriptstyle o}{\Omega }(n^{\Delta +1})\) space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use \(\Omega (n^{2/3})\) query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.

24 October 2023 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
PAPeyman Afshani
Peyman Afshani
PCPingan Cheng
Pingan Cheng

6 July 2026
Verified
Conference Paper
Open access
PAPeyman Afshani
Peyman Afshani
MMMagnus Christian Ring Merrild
Magnus Christian Ring Merrild
We study the problem of proving lower bounds in the Priority CRCW PRAM for the query time of several fundamental and well-studied data structures, motivated by the observation that, for many basic data structure problems, no proven limits on parallelism exist. We use the cell-probe model, which has been studied extensively in the sequential setting and where for all the problems under consideration, Ω(log n/log log n) query time lowers bound exist. However, we report that in the parallel settings, some of these problems become "easy", i.e., admit solutions with constant query time in the Common CRCW PRAM using polylogarithmic number of processors, while others become "hard", via the following result. We prove query time lower bounds (in the Priority CRCW PRAM model) via a careful combination of some of the cell-probe lower bound techniques with ideas from the PRAM area. While the actual statement of the lower bounds are complicated, they all can be simplified to an Ω(log log n) query time lower bound under the most reasonable settings, and with polylogarithmic processors. The fact that all these problems admit an Ω(log n/log log n) query lower bound in the sequential settings implies that most of the cell-probe lower bound techniques cannot be generalized to the CRCW PRAM model of computation, meaning, the landscape of data structure lower bounds in the CRCW PRAM models of computation is more complicated. We end the paper with a number of interesting open problems for future research.

3 September 2019 in arXiv
Verified
Preprint
Open access
PDF file
PAPeyman Afshani
Peyman Afshani
RFRolf Fagerberg
Rolf Fagerberg
DHDavid Hammer
David Hammer
RJRiko Jacob
Riko Jacob
IKIrina Kostitsyna
Irina Kostitsyna
NSNodari Sitchinava
Nodari Sitchinava
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible.