What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?

Question

I am faced with the following problem:

• A uniformly random $n \times n$ matrix $M$ over a finite field $\mathbb{F}$ is sampled. The algorithm has oracle access to the matrix entries, and each query to an entry "costs 1".
• The algorithm has space $C\cdot n$, where $C > 1$ is some universal constant. It can run in unbounded time on its $C\cdot n$-size worktape (i.e. we only count its query complexity).
• The algorithm receives $y = M\cdot x$ where $x$ is a uniformly random vector over $\mathbb{F}$. Its goal is to output $x$.

My question is: what is a reasonable conjecture about (a lower bound on) the query complexity of this algorithm?

A few notes about what I know (I tried to do my homework before asking the question):

Matrix multiplication being in $\mathsf{DSPACE}(\log^2n)$, there is definitely a polytime-query algorithm for solving a random system of equations in space $C\cdot n$, and it is probably quite easy to find one. I'm however more interested in bounding below the number of queries. I assume any unconditional bound would be way too strong to hope for, but I would be perfectly fine with a reasonable conjecture given our current state of knowledge. I also know of Grigoriev's lower bound method, which can be used to show that, in some restricted model of straight-line computation, we have the relation $S\cdot T = \Omega(n^3)$ (I read about it here). However, (1) this is for a very restricted model, and (2) I would expect a significantly better lower bound to hold: especially, in my setting, it only shows that you need $T = \Omega(n^2)$ time, which, well, is obvious.

I would be happy with any partial answer, pointers to the literature, or educated guess of people who worked in related areas and have an intuition about this kind of problem (i.e. I don't necessarily need that the conjecture is related to anything well-established, as long as one can explain why it makes sense in light of what we currently know). I'm fine with any choice of finite field (e.g. $\mathbb{F}_2$, or large fields, if any particular choice helps).

Extensions: I'm also interested in the related question where the goal is to output the inner product $\langle z, x\rangle$, where $z$ is also a random vector given as input to the algorithm. I am further also interested in the setting where the space is $n^{1+\varepsilon}$, for any $\varepsilon < 1$.

=== EDIT ===

As Clément C. correctly pointed out in the comments, Ran Raz's celebrated time-space lower bounds on parity learning is strongly related to my question. And indeed, it is the starting point of my question. So, it might be helpful here that I clarify the distinction between what Raz proved and what I want:

• Raz's paper shows that if you have $< n^2/20$ memory and receive a stream $(m_i, \langle m_i, x \rangle)$ where $x$ is a secret vector and the $m_i$ are the rows of a random matrix $M$, you need exponentially many samples to recover $x$.
• This is neat, but this is for single-pass streaming: what happens if you can make two passes on the data? Well, Garg, Raz, and Tal have a very nice follow-up showing that with less than $\Omega(n^{1.5})$ space, you would need $2^{\sqrt{\log n}}$ samples to recover $x$. Notice how the bound degrades quickly!
• As of today, nothing is known for 3 passes or more.

Now, in my question, the adversary is considerably more powerful: he is given arbitrary oracle access to the matrix $M$ (which is now limited to $n$ samples for simplicity). So, the adversary can make an arbitrary number of passes on $M$, query it in the order that they want, etc. In this regime, one cannot hope for a bound a la Ran Raz: it should actually be feasible to recover $x$ with polynomially-many passes on $M$ even with $C\cdot n$ space (because matrix-vector multiplication is in $\mathsf{DSPACE}(\mathsf{polylog}(n))$. Hence, the tradeoff must inherently be different. Furthermore, in light of the current limits of the techniques in this line of work, I don't expect any of it to magically generalize to "arbitrary oracle access to the matrix": handling two passes is already hard, and three passes is open... So, instead, I'm just hoping for a reasonable conjecture on what an expert would estimate to be likely true, a "rule of thumb" if you like, of the form "we expect any such adversary to require at least $n^d$ accesses to $M$", with some constant $d> 2$. Hope this clarifies!

Answer 1

Interestingly, a pretty good answer to my question was already given in Wiedemann's seminal paper on solving sparse linear systems. I am actually quite familiar with the paper, but I had totally missed the connection!

Wiedemann's result is commonly described as an algorithm to solve $w$-sparse linear systems in time $O(w\cdot n + n^2)$. But in fact, it does much more than that. A good abstraction of Wiedemann's result is that it gives an algorithm solving linear systems in the black-box model of linear algebra. Concretely, given a singular matrix $A \in \mathbb{F}^{n\times n}$ and $b\in\mathbb{F}^n$, Wiedemann gives an algorithm that finds a solution $x$ to $Ax = b$ using

• $\tilde{O}(n^2)$ arithmetic operations (either over $\mathbb{F}$ if the field is large enough, else over an extension field),
• $O(n)$ space, and
• $O(n)$ calls to a black-box for $A$ which, on input a vector $z$, outputs $Az$.

I learned about the formalism of black-box linear algebra (where access to the matrix is given via a black-box for computing matrix-vector product) in the works of Eberly, see e.g. here (I don't know whether it originated in his work, though). That Wiedemann's algorithm runs in linear space can be extracted from the algorithm; I did not find it stated explicitly in his work, but it is mentioned explicitly e.g. here.

Now, in my model, $A$ is singular with very high probability (assuming $\mathbb{F}$ is large enough), and a call to the black-box can easily be emulated using $O(n)$ space and $n^2$ oracle queries to the matrix. Overall, this yields an $O(n^3)$-query, $O(n^3)$-work, $O(n)$-space algorithm for solving linear systems in the model of my question.

I find this extremely interesting. I had never observed that Wiedemann's algorithm implies that one can match the efficiency of Gaussian elimination using only $O(n)$ local space, and I've never seen this observation elsewhere, but it looks like a pretty neat result for general matrices (in contrast, Wiedemann's result is almost always described as a way to save time when solving linear systems with structured matrices). This $O(n^3)$ is also much smaller than what I would have been initially tempted to conjecture.

Because my original question asks for a conjecture, let me put forth the following conjecture:

• (weak version) In the black-box model of linear algebra with linear space, Wiedemann's algorithm is essentially optimal in terms of calls to the black-box (i.e., there is no $O(n)$ space algorithm making $n^{1-\varepsilon}$ calls to the black-box)
• (strong version) In the oracle model of my question (with linear space), Wiedemann's algorithm is essentially optimal in terms of queries to the matrix (i.e., there is no $O(n)$ space algorithm making $n^{3-\varepsilon}$ calls to the black-box)

These conjectures seem sensible to me, since approaching the matrix multiplication time for solving linear systems while using linear space would sound like a huge breakthrough. Of course, they are nothing more than (vaguely educated) conjectures, but I though it'd be interesting to share them here!