BackgroundThe external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses).  These running times are generally given in terms of $M$, the size of memory, and $B$, the number of words that can be transferred to memory at one time.  Sometimes $L$ and $Z$ are used for $B$ and $M$ respectively.  For example, sorting requires a cost of $\Theta(N/B\log_{M/B} N/B)$ and naive matrix multiplication requires $\Theta(n^3/B\sqrt{M})$.  This model is used to analyze cache-oblivious algorithms, which do not have knowledge of $B$ or $M$.  Generally the goal is for the cache-oblivious algorithm to perform optimally in the external memory model; this is not always possible, as in the Permutation problem for example (shown in Brodal, Faderberg 2003).  See this writeup by Erik Demaine for a further explanation of cache-oblivious algorithms, including discussions of sorting and matrix multiplication.We can see that changing $M$ causes a logarithmic speedup for sorting and a polynomial speedup for matrix multiplication.  (This result is originally from Hong, Kung 1981 and actually predates both cache obliviousness and the formalization of the external memory model). My question is this:Is there any case where the speedup is exponential in $M$? The running time would be something like $f(N,B)/2^{O(M)}$. I am particularly interested in a cache-oblivious algorithm or data structure that fits this description but would be happy with a cache-aware algorithm/data structure or even a best-known lower bound.It is generally assumed in most models that the word size $w = \Omega(\log N)$ if $N$ is the input size and clearly $M > w$.  Then a speedup of $2^M$ gives a polynomial speedup in $N$.  This makes me believe that if the problem I'm looking for exists, it is not polynomial.  (Otherwise we can change the cache size by a constant to obtain a constant number of I/Os, which seems unlikely).
Exponential Speedup in External Memory
ds.algorithms;ds.data structures;cache oblivious