# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

227 questions
Filter by
Sorted by
Tagged with
1 vote
52 views

### Find linear combination with small support

Let $v_1,\dots,v_n$ be a basis of a vector subspace of $\Bbbk^N$, say for $\Bbbk$ a finite field. I would like an algorithm to find a linear combination of the $v_i$'s with small support, i.e. with ...
• 191
96 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 ...
• 1
49 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 ...
• 918
148 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 ...
• 151
1 vote
63 views

### Circuit depth of linear algebra operations

I was checking the following paper [1] 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 ...
• 151
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 ...
• 12.8k
199 views

1 vote
53 views

• 101
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 ...
• 235
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-...
• 265
1 vote
98 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 ...
• 11
208 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 ...
• 32.4k
872 views

### Non-Orthogonal Vectors Problem

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$ ...
• 5,127