This work makes two distinct yet related contributions. The first contribution is a new information-theoretic model, the query-with-sketch model, and tools to show lower bounds within it. The second contribution is conceptual, technically builds on the first contribution, and is a barrier in the derandomization of randomized logarithmic space (BPL).

(1) The query-with-sketch model generalizes the query complexity model for computing multi-bit functions $f:\{0,1\}^N\to\{0,1\}^M$. In this model, computation unfolds in two phases. Initially, the algorithm sends an agent to evaluate an arbitrary but length-restricted sketch of the input. Subsequently, the algorithm proceeds with queries. The main technical contribution is a lower bound in this model for the Approximate Matrix Powering (AMP) problem. To that end, we introduce a constrained form of conditional min-entropy that characterizes the number of queries in the model. We bound this entropy by developing tools that blend geometry, a generalization of tools from Lipschitz analysis for polynomials and low-distortion spaces, and probability theory. The main result is that AMP requires polynomial query complexity or super-polylogarithmic sketch size. We note that AMP and the query-with-sketch model are natural and interesting in their own right, in addition to the following conceptual contribution.

(2) Derandomizing BPL is an open question in computational complexity. The most successful derandomization algorithms of BPL make recursive use of pseudorandom generators or similar pseudorandom objects. The best-known derandomization places BPL inside DSPACE$(\frac{\log^{3/2} n}{\sqrt{\log\log n}})$. We ask whether these algorithms can be substantially improved if we keep fixed the pseudorandom object and the main idea, which is to approximate $M^n$ of the computation matrix $M$ by relying on intermediate powers such as $M^{n/2}$. We answer this question in the negative in a recursive generalization of the query-with-sketch model. We show that in this recursive and space-bounded model AMP needs super-polynomially many queries (time) or super-polylogarithmic sketch size (space). Specifically, in our model an algorithm that uses approximations of elements of the matrix $M^{n/2}$ to approximate an element of $M^n$, it must first determine the values of these elements in $M^{n/2}$ and it can do this recursively. Other than this restriction, an algorithm is free to determine arbitrarily how to organize the recursion and how to use the bounded space. The conceptual takeaway is the "intermediate powers barrier", which indicates that fully derandomizing BPL cannot rely on a natural, recursive use of approximated intermediate powers.