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 ...
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 ...
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.
...
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....
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) ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
linear-equations × 13ds.algorithms × 5
linear-algebra × 3
cc.complexity-theory × 2
sparse-matrix × 2
optimization × 1
quantum-computing × 1
sat × 1
cr.crypto-security × 1
linear-programming × 1
big-picture × 1
approximation-hardness × 1
randomness × 1
matrices × 1
quantum-information × 1
na.numerical-analysis × 1
circuits × 1
cryptographic-attack × 1
compressed-sensing × 1
generalizations × 1