2022 Developer Survey is open! Take survey.
11 votes
Accepted

Complexity of solving linear equations

I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More ...
user avatar
9 votes
Accepted

Applications of HHL's algorithm for solving linear equations

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical ...
user avatar
6 votes
Accepted

Cryptographic systems that don't leak linear combinations of encrypted bits

Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing. ...
user avatar
  • 10.3k
6 votes

Complexity of solving linear equations

A result known for over 30 years is that Guassian Elimination over $\mathbb F_2$ can be done by a various decompositions which takes $O(n^\omega)$, where $\omega$ is the matrix multiplication constant....
user avatar
  • 9,358
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) ...
user avatar

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