Skip to main content
6 votes
Accepted

Complexity of $\{0,\pm1\}$ determinant in sparse cases?

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$. If the answer to your question were positive, then you could compute the ...
Joshua Grochow's user avatar
3 votes
Accepted

Problem conditions to use Laplacian solvers

It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition ...
smapers's user avatar
  • 849
2 votes
Accepted

When is it hard to invert a sparse matrix?

Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) ...
Thomas Klimpel's user avatar
1 vote
Accepted

Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

Yes! But I can see why it is confusing. A strongly explicit graph family $\{G_n = (V_n,E_n)\}$ (parameterized e.g. by number of vertices $n$) is described by an efficient ($\mathrm{polylog}(n)$ time) ...
smapers's user avatar
  • 849
1 vote

The connection between compressed sensing and sparse representation

Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can ...
argentum2f's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible