Data Structures, Adaptive (analysis of) Algorithms: Some Challenges for Combinatorics

Abstract:

Succinct data structures replace static instances of pointer based data structures, improving performance in both time and space in the word RAM model (a restriction of the RAM model where the size of a word is restricted). The adaptive analysis of algorithms consider the complexity in a finer way than merely grouping the instances by size, yielding more precise lower and upper bound on the complexity of a problem. We give a quick overview of those two techniques, some brief examples of how they can be combined on various search problems to obtain near optimal solutions, and some general perspective on the application and development of those techniques to other problems and models.

http://www.cs.uwaterloo.ca/~jbarbay/Recherche/Publishing/Publications/#succinctIndexesAndAdaptiveAlgorithms