The paper Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses <http://www.itu.dk/people/pagh/papers/sparse.pdf> is the only one that uses Kolmogorov Complexity to obtain a lower bound in the space of a data structure that rank with erros.My question is: What are the other Algorithmic options of complexity that replace the Kolmogorov Complexity? Is Kolmogorov-Sinai Entropy a option?
What are the substitues for Kolmogorov Complexity to analyse Hashing
algorithm analysis;data structures;hash tables;kolmogorov complexity