<p>Interestingly, a pretty good answer to my question was already given in <a href="https://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Wiedemann86.pdf" rel="nofollow noreferrer">Wiedemann's seminal paper on solving sparse linear systems</a>. I am actually quite familiar with the paper, but I had totally missed the connection!</p>
<p>Wiedemann's result is commonly described as an algorithm to solve <span class="math-container">$w$</span>-sparse linear systems in time <span class="math-container">$O(w\cdot n + n^2)$</span>. 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 <span class="math-container">$A \in \mathbb{F}^{n\times n}$</span> and <span class="math-container">$b\in\mathbb{F}^n$</span>, Wiedemann gives an algorithm that finds a solution <span class="math-container">$x$</span> to <span class="math-container">$Ax = b$</span> using</p>
<ul>
<li><span class="math-container">$\tilde{O}(n^2)$</span> arithmetic operations (either over <span class="math-container">$\mathbb{F}$</span> if the field is large enough, else over an extension field),</li>
<li><span class="math-container">$O(n)$</span> space, and</li>
<li><span class="math-container">$O(n)$</span> calls to a <em>black-box for <span class="math-container">$A$</span></em> which, on input a vector <span class="math-container">$z$</span>, outputs <span class="math-container">$Az$</span>.</li>
</ul>
<p>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. <a href="https://arxiv.org/abs/1607.04514" rel="nofollow noreferrer">here</a> (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. <a href="https://www.dima.unige.it/%7Emorafe/MaterialeCTC/KaSa91.pdf" rel="nofollow noreferrer">here</a>.</p>
<p>Now, in my model, <span class="math-container">$A$</span> is singular with very high probability (assuming <span class="math-container">$\mathbb{F}$</span> is large enough), and a <em>call to the black-box</em> can easily be emulated using <span class="math-container">$O(n)$</span> space and <span class="math-container">$n^2$</span> oracle queries to the matrix. Overall, this yields an <span class="math-container">$O(n^3)$</span>-query, <span class="math-container">$O(n^3)$</span>-work, <span class="math-container">$O(n)$</span>-space algorithm for solving linear systems in the model of my question.</p>
<p>I find this extremely interesting. I had never observed that Wiedemann's algorithm implies that one can <em>match</em> the efficiency of Gaussian elimination using only <span class="math-container">$O(n)$</span> 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 <em>time</em> when solving linear systems with <em>structured</em> matrices). This <span class="math-container">$O(n^3)$</span> is also much smaller than what I would have been initially tempted to conjecture.</p>
<p>Because my original question asks for a conjecture, let me put forth the following conjecture:</p>
<ul>
<li>(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 <span class="math-container">$O(n)$</span> space algorithm making <span class="math-container">$n^{1-\varepsilon}$</span> calls to the black-box)</li>
<li>(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 <span class="math-container">$O(n)$</span> space algorithm making <span class="math-container">$n^{3-\varepsilon}$</span> calls to the black-box)</li>
</ul>
<p>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!</p>

CC BY-SA 4.0
2022-12-22T02:50:04.440Z
An $O(n^3)$-time, $\tilde{O}(n)$-space algorithm based on LDL decomposition is also described in the John Savage book (Theorem 6.5.4), and it actually computes the entire matrix inverse (for which the Borodin-Cook bound is tight).
Wei Zhan
CC BY-SA 4.0
2022-12-22T07:48:10.650Z
Interesting, thanks! I actually don't have the book, I only read the pdf of chapter 10 (about space time tradeoffs). I will look it up!
Geoffroy Couteau
CC BY-SA 4.0
2022-12-21T22:55:31.153Z
2022-12-21T23:38:18.607Z
2022-12-21T23:38:18.607Z
Geoffroy Couteau
<p>I am faced with the following problem:</p>
<ul>
<li>A uniformly random <span class="math-container">$n \times n$</span> matrix <span class="math-container">$M$</span> over a finite field <span class="math-container">$\mathbb{F}$</span> is sampled. The algorithm has oracle access to the matrix entries, and each query to an entry &quot;costs 1&quot;.</li>
<li>The algorithm has space <span class="math-container">$C\cdot n$</span>, where <span class="math-container">$C &gt; 1$</span> is some universal constant. It can run in unbounded time on its <span class="math-container">$C\cdot n$</span>-size worktape (<em>i.e.</em> we only count its query complexity).</li>
<li>The algorithm receives <span class="math-container">$y = M\cdot x$</span> where <span class="math-container">$x$</span> is a uniformly random vector over <span class="math-container">$\mathbb{F}$</span>. Its goal is to output <span class="math-container">$x$</span>.</li>
</ul>
<p><strong>My question is:</strong> what is a <em>reasonable conjecture</em> about (a lower bound on) the query complexity of this algorithm?</p>
<p>A few notes about what I know (I tried to do my homework before asking the question):</p>
<p>Matrix multiplication being in <span class="math-container">$\mathsf{DSPACE}(\log^2n)$</span>, there is definitely a polytime-query algorithm for solving a random system of equations in space <span class="math-container">$C\cdot n$</span>, 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 <em>reasonable conjecture</em> 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 <span class="math-container">$S\cdot T = \Omega(n^3)$</span> (I read about it <a href="https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter10.pdf" rel="nofollow noreferrer">here</a>). 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 <span class="math-container">$T = \Omega(n^2)$</span> time, which, well, is obvious.</p>
<p>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 (<em>i.e.</em> 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. <span class="math-container">$\mathbb{F}_2$</span>, or large fields, if any particular choice helps).</p>
<p>Extensions: I'm also interested in the related question where the goal is to output the inner product <span class="math-container">$\langle z, x\rangle$</span>, where <span class="math-container">$z$</span> is also a random vector given as input to the algorithm. I am further also interested in the setting where the space is <span class="math-container">$n^{1+\varepsilon}$</span>, for any <span class="math-container">$\varepsilon &lt; 1$</span>.</p>
<p>=== EDIT ===</p>
<p>As Clément C. correctly pointed out in the comments, Ran Raz's celebrated <a href="https://dl.acm.org/doi/10.1145/3186563" rel="nofollow noreferrer">time-space lower bounds on parity learning</a> 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:</p>
<ul>
<li>Raz's paper shows that if you have <span class="math-container">$&lt; n^2/20$</span> memory and receive a stream <span class="math-container">$(m_i, \langle m_i, x \rangle)$</span> where <span class="math-container">$x$</span> is a secret vector and the <span class="math-container">$m_i$</span> are the rows of a random matrix <span class="math-container">$M$</span>, you need exponentially many samples to recover <span class="math-container">$x$</span>.</li>
<li>This is neat, but this is for single-pass streaming: what happens if you can make <em>two passes</em> on the data? Well, Garg, Raz, and Tal have a very nice <a href="https://par.nsf.gov/servlets/purl/10121212" rel="nofollow noreferrer">follow-up</a> showing that with less than <span class="math-container">$\Omega(n^{1.5})$</span> space, you would need <span class="math-container">$2^{\sqrt{\log n}}$</span> samples to recover <span class="math-container">$x$</span>. Notice how the bound degrades quickly!</li>
<li>As of today, nothing is known for 3 passes or more.</li>
</ul>
<p>Now, in my question, the adversary is considerably more powerful: he is given <em>arbitrary oracle access</em> to the matrix <span class="math-container">$M$</span> (which is now limited to <span class="math-container">$n$</span> samples for simplicity). So, the adversary can make an arbitrary number of passes on <span class="math-container">$M$</span>, query it in the order that they want, etc. In this regime, one cannot hope for a bound <em>a la</em> Ran Raz: it should actually be feasible to recover <span class="math-container">$x$</span> with polynomially-many passes on <span class="math-container">$M$</span> even with <span class="math-container">$C\cdot n$</span> space (because matrix-vector multiplication is in <span class="math-container">$\mathsf{DSPACE}(\mathsf{polylog}(n))$</span>. 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 &quot;arbitrary oracle access to the matrix&quot;: 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 &quot;rule of thumb&quot; if you like, of the form &quot;we expect any such adversary to require at least <span class="math-container">$n^d$</span> accesses to <span class="math-container">$M$</span>&quot;, with some constant <span class="math-container">$d&gt; 2$</span>. Hope this clarifies!</p>

CC BY-SA 4.0
2022-12-07T22:29:42.913Z
I think you'd have to query all the entries. By linearity, if you change any one entry of M, unless the corresponding entry of x happens to be 0, you'd change the output.
Joshua Grochow
CC BY-SA 4.0
2022-12-07T23:01:08.303Z
Of course! But I'm actually wondering whether you have to query *more* than all entries: because of the $C\cdot n$ space restriction, you cannot just "download the full matrix", so it's very likely that, to compute the solution $x$, you will have to re-query some entries many times. My hope is actually that a number of queries significantly larger than $n^2$ is required given this space restriction.
Geoffroy Couteau
CC BY-SA 4.0
2022-12-08T02:41:52.020Z
A related result is that the Borodin-Cook method gives an $ST=\Omega(n^4)$ lower bound for matrix inversion (it's also in the John Savage book you linked). That should imply a worst-case $ST=\Omega(n^3)$ lower bound for your problem in the branching program model.
Wei Zhan
CC BY-SA 4.0
2022-12-08T09:44:43.887Z
Interesting! This is stronger than what I knew, but unfortunately in the $S \approx n$ regime, it still only gives $T = \Omega(n^2)$, which as Joshua observed should be relatively straightforward. My hope is that a larger polynomial gap can be reasonably conjectured, even if we don't have a provable time-space tradeoff.
Geoffroy Couteau
CC BY-SA 4.0
2022-12-10T23:53:25.477Z
This seems relevant? https://dl.acm.org/doi/10.1145/3186563
Clement C.
CC BY-SA 4.0
2022-12-11T11:26:23.667Z
This paper was actually my starting point, so it's indeed relevant, but it does not solve my problem! I'm editing the question to clarify this point. Thanks :)
Geoffroy Couteau
CC BY-SA 4.0
2022-12-11T16:46:13.340Z
What is the expected role of $M$ and $x$ being sampled uniformly at random? Do you want an average-case lower bound?
Bruno
CC BY-SA 4.0
2022-12-11T17:08:26.457Z
Yes, ideally I would want that (the same way that Raz's lower bound is average case). But a worst case (conjectured) lower bound would be an excellent starting point (hopefully together with some intuition about what could be a candidate hard distribution for M and x).
Geoffroy Couteau
<lower-bounds><space-bounded><query-complexity><linear-equations>
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)$?
Geoffroy Couteau
# 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)$?

(Asked by: username_0 on 2022-12-07)

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](https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter10.pdf)). 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](https://dl.acm.org/doi/10.1145/3186563) 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](https://par.nsf.gov/servlets/purl/10121212) 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!

**Tags:** lower-bounds, space-bounded, query-complexity, linear-equations
> **Comments:**
> **username_1**: I think you'd have to query all the entries. By linearity, if you change any one entry of M, unless the corresponding entry of x happens to be 0, you'd change the output.  
> **username_0**: Of course! But I'm actually wondering whether you have to query *more* than all entries: because of the $C\cdot n$ space restriction, you cannot just "download the full matrix", so it's very likely that, to compute the solution $x$, you will have to re-query some entries many times. My hope is actually that a number of queries significantly larger than $n^2$ is required given this space restriction.  
> **username_2**: A related result is that the Borodin-Cook method gives an $ST=\Omega(n^4)$ lower bound for matrix inversion (it's also in the John Savage book you linked). That should imply a worst-case $ST=\Omega(n^3)$ lower bound for your problem in the branching program model.  
> **username_0**: Interesting! This is stronger than what I knew, but unfortunately in the $S \approx n$ regime, it still only gives $T = \Omega(n^2)$, which as Joshua observed should be relatively straightforward. My hope is that a larger polynomial gap can be reasonably conjectured, even if we don't have a provable time-space tradeoff.  
> **username_3**: This seems relevant? https://dl.acm.org/doi/10.1145/3186563  
> **username_0**: This paper was actually my starting point, so it's indeed relevant, but it does not solve my problem! I'm editing the question to clarify this point. Thanks :)  
> **username_4**: What is the expected role of $M$ and $x$ being sampled uniformly at random? Do you want an average-case lower bound?  
> **username_0**: Yes, ideally I would want that (the same way that Raz's lower bound is average case). But a worst case (conjectured) lower bound would be an excellent starting point (hopefully together with some intuition about what could be a candidate hard distribution for M and x).  

---

## 1 answers

### Answer by username_0 on 2022-12-21. Score: 2 | Accepted answer

Interestingly, a pretty good answer to my question was already given in [Wiedemann's seminal paper on solving sparse linear systems](https://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Wiedemann86.pdf). 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](https://arxiv.org/abs/1607.04514) (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](https://www.dima.unige.it/%7Emorafe/MaterialeCTC/KaSa91.pdf).

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!

> **Comments:**
> **username_2**: An $O(n^3)$-time, $\tilde{O}(n)$-space algorithm based on LDL decomposition is also described in the John Savage book (Theorem 6.5.4), and it actually computes the entire matrix inverse (for which the Borodin-Cook bound is tight).  
> **username_0**: Interesting, thanks! I actually don't have the book, I only read the pdf of chapter 10 (about space time tradeoffs). I will look it up!  

---

