scientific article; zbMATH DE number 5485435

MaRDI QIDQ3549595zbMATH OpenFDO

Authors Mihai Patrascu

Publication date 5 January 2009

zbMATH Keywords

cell-probe modeldynamic boundsgroup modellower boundsorthogonal range counting in two dimensionsrange queriesstatic bounds

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited in

(18)

• Orthogonal range searching in linear and almost-linear space
• Semi-group range sum revisited: query-space lower bound tightened
• Lower bounds for matrix factorization
• Wavelet trees for all
• Fully functional static and dynamic succinct trees
• Compact binary relation representations with rich functionality
• Space efficient data structures for dynamic orthogonal range counting
• Entropy-bounded representation of point grids
• Polynomial data structure lower bounds in the group model
• Lower bounds for matrix factorization
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Substring range reporting
• Towards optimal range medians
• Absent Subsequences in Words
• The edit distance to k-subsequence universality
• Super-logarithmic lower bounds for dynamic graph problems
• Succinct data structures for segments

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549595)