research
∙
05/04/2023
On Range Summary Queries
We study the query version of the approximate heavy hitter and quantile ...
share
research
∙
02/22/2023
Lower Bounds for Intersection Reporting among Flat Objects
Recently, Ezra and Sharir [ES22a] showed an O(n^3/2+σ) space and O(n^1/2...
research
∙
10/26/2022
An Optimal Lower Bound for Simplex Range Reporting
We give a simplified and improved lower bound for the simplex range repo...
research
∙
10/11/2022
Hierarchical Categories in Colored Searching
In colored range counting (CRC), the input is a set of points where each...
research
∙
03/14/2022
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
We consider the following surveillance problem: Given a set P of n sites...
research
∙
03/14/2022
On Semialgebraic Range Reporting
In the problem of semialgebraic range searching, we are to preprocess a ...
research
∙
12/01/2020
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
In the semialgebraic range searching problem, we are to preprocess n poi...
research
∙
11/01/2020
A Lower Bound for Dynamic Fractional Cascading
We investigate the limits of one of the fundamental ideas in data struct...
research
∙
09/11/2020
2D Fractional Cascading on Axis-aligned Planar Subdivisions
Fractional cascading is one of the influential techniques in data struct...
research
∙
05/05/2020
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
We consider the problem of finding patrol schedules for k robots to visi...
research
∙
03/19/2019
Independent Range Sampling, Revisited Again
We revisit the range sampling problem: the input is a set of points wher...
research
∙
03/19/2019
A New Lower Bound for Semigroup Orthogonal Range Searching
We report the first improvement in the space-time trade-off of lower bou...
research
∙
02/28/2019
Lower Bounds for Multiplication via Network Coding
Multiplication is one of the most fundamental computational problems, ye...
research
∙
01/09/2019
Fragile Complexity of Comparison-Based Algorithms
We initiate a study of algorithms with a focus on the computational comp...
research
∙
12/20/2018
The Query Complexity of a Permutation-Based Variant of Mastermind
We study the query complexity of a permutation-based variant of the gues...
research
∙
07/15/2017