17 citations · 32 across the 18 of their papers we have counts for
5 papers · 2 filters
Independent Range Sampling, Revisited Again
Peyman Afshani, Jeff M. Phillips
We revisit the range sampling problem: the input is a set of points where each point is associated with a real-valued weight. The goal is to store them in a structure such that giv…
A New Lower Bound for Semigroup Orthogonal Range Searching
Peyman Afshani
We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle's result from 1990. Th…
Lower Bounds for Multiplication via Network Coding
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma +1
Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two -bit numbers…
Locality
Peyman Afshani, John Iacono, Varunkumar Jayapaul +2
The program performance on modern hardware is characterized by \emph{locality of reference}, that is, it is faster to access data that is close in address space to data that has be…
Fragile Complexity of Comparison-Based Algorithms
Peyman Afshani, Rolf Fagerberg, David Hammer +5
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 ma…