All Questions

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...

Let $N=\{1,2,\ldots,n\}$. Suppose we are given $n$ equations, with each equation taking the form $\sum_{A\subseteq N}\left(c_A \prod_{i\in A}x_i \right) = 0$, where each $c_A$ is a real number ...

Let $n_1>n_2\geq 1$ be integers. Are there a known algorithms for generating $n_2\times n_1$-dimensional random matrices $A$ such that $$ \|Ax - Ay\|<\|x-y\| \mbox{ if $x\neq y$}? $$

For a given $n \times m$ matrix A with $m>>n$ and a given vector $\vec b \in \mathbb{F}^{n \times 1}$, and given that $A\vec{x}=\vec{b}$ for at least one $\vec{x} \in \mathbb{F}^{m \times 1}$, ...

I need this for experimentation in some work, so it is not without purpose. Consider the in-spiraling and out-spiraling $4\times 4$ matrices $$\begin{pmatrix} 1&2&3&4 \\ 12&13&14&...

Let $A \in \mathbb{Z}^{n \times n}$ be a positive semidefinite sparse matrix. I am looking for asymptotically fast algorithms for computing the nullspace basis of $A$ (or just random elements in the ...