18 citations · 72 across the 35 of their papers we have counts for
54 papers
A General Technique for Searching in Implicit Sets via Function Inversion
Boris Aronov, Jean Cardinal, Justin Dallant +1
In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a n…
External-memory dictionaries with worst-case update cost
Rathish Das, John Iacono, Yakov Nekrich
The -tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-memory-model data structure that supports updates orders of magnitude faster than B-tree with a query…
How Fast Can We Play Tetris Greedily With Rectangular Pieces?
Justin Dallant, John Iacono
Consider a variant of Tetris played on a board of width and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only b…
Conditional Lower Bounds for Dynamic Geometric Measure Problems
Justin Dallant, John Iacono
We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word-RAM model, conditioned on the hardness o…
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model
Boris Aronov, Mark de Berg, Jean Cardinal +3
We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Gi…
Worst-Case Efficient Dynamic Geometric Independent Set
Jean Cardinal, John Iacono, Grigorios Koumoutsos
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a consta…