First sub-trivial algorithms for All-Edges Sparse Triangle, Sparse Monochromatic Triangle, Exact Triangle, and 4-cycle detection using AC0 word operations.
Threesomes, degenerates, and love triangles
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
A Fiat-Naor-based inversion technique yields data structures for range searching, counting, and related queries on implicit sets f([N]) with ~O(N^{1-α/3}) space and ~O(N^α) query time for any α ∈ (0,1).
citing papers explorer
-
Beating Trivial Time for Tricky Triangle Tasks
First sub-trivial algorithms for All-Edges Sparse Triangle, Sparse Monochromatic Triangle, Exact Triangle, and 4-cycle detection using AC0 word operations.
-
A General Technique for Searching in Implicit Sets via Function Inversion
A Fiat-Naor-based inversion technique yields data structures for range searching, counting, and related queries on implicit sets f([N]) with ~O(N^{1-α/3}) space and ~O(N^α) query time for any α ∈ (0,1).