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 ...
- 14.7k
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 ...
- 1,355
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.
...
- 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....
- 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) ...
- 3,013
Only top scored, non community-wiki answers of a minimum length are eligible