# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

226 questions
Filter by
Sorted by
Tagged with
91 views

### Algebra in complexity theory

Recently an idea came to my mind. Suppose $V$ is vector space and $\dim V = n$. Then, since $V \simeq \mathbb{R}^n$, any conjunction of $n$ boolean formulas $\phi_1, \ldots, \phi_n$ about vectors from ...
48 views

### Approximate Matrix Multiplication with approximation guarantees that ignore large elements?

Approximate matrix multiplication is a technique to replace a matrix product $A^t B$ with a smaller product $(\Pi A)^t(\Pi B)$. Intuitively, if $\Pi$ is chosen from a suitable distribution that has ...
147 views

### On the plausability of quantum RAM

I'm fairly new to quantum computation and quantum complexity theory, but I came across some articles that suggest that quantum RAM (QRAM) is not very realistic assumption. For example some works show ...
1 vote
62 views

### Circuit depth of linear algebra operations

I was checking the following paper  about low-depth PRFs from lattices. In table 1 on page 4, there is comparison with other constructions, and it shows evaluation depths of certain PRFs. I'm not ...
26 views

### Linear modular equalities with $0/1$ solution

Let $Ax\equiv b\bmod q$ be a $n\times n$ modular linear system known to have $0/1$ solution where $q$ is a large prime. We can solve in $NC^2$ for general linear systems using determinant and matrix ...
196 views

1 vote
53 views

218 views

### Is there a fast algorithm for inverting a sparse matrix?

I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
33 views

### Does optimal fitting flat must pass through the mean of the point set?

I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line. Project clustering is a natural generalization of k-...
1 vote
97 views

### Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity

In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf . I don't state the full lemma ...
205 views

### Do Banach spaces and linear contraction maps form a model of ILL with an exponential?

Recently, I read on the nLab that the category of Banach spaces and linear contractions is small complete, small cocomplete, and monoidal closed. This means that Banach spaces and short linear maps ...
Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting  [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...