  In this paper we investigate the problem of building a static data structure
that represents a string s using space close to its compressed size, and allows
fast access to individual characters of s. This type of structures was
investigated by the recent paper of Bille et al. Let n be the size of a
context-free grammar that derives a unique string s of length L. (Note that L
might be exponential in n.) Bille et al. showed a data structure that uses
space O(n) and allows to query for the i-th character of s using running time
O(log L). Their data structure works on a word RAM with a word size of logL
bits. Here we prove that for such data structures, if the space is poly(n),
then the query time must be at least (log L)^{1-\epsilon}/log S where S is the
space used, for any constant eps>0. As a function of n, our lower bound is
\Omega(n^{1/2-\epsilon}). Our proof holds in the cell-probe model with a word
size of log L bits, so in particular it holds in the word RAM model. We show
that no lower bound significantly better than n^{1/2-\epsilon} can be achieved
in the cell-probe model, since there is a data structure in the cell-probe
model that uses O(n) space and achieves O(\sqrt{n log n}) query time. The "bad"
setting of parameters occurs roughly when L=2^{\sqrt{n}}. We also prove a lower
bound for the case of not-as-compressible strings, where, say,
L=n^{1+\epsilon}. For this case, we prove that if the space is n polylog(n),
then the query time must be at least \Omega(log n/loglog n).
  The proof works by reduction to communication complexity, namely to the LSD
problem, recently employed by Patrascu and others. We prove lower bounds also
for the case of LZ-compression and Burrows-Wheeler (BWT) compression. All of
our lower bounds hold even when the strings are over an alphabet of size 2 and
hold even for randomized data structures with 2-sided error.
