Peng, Vempala (Sparse Linear system of equations)
Jump to navigation
Jump to search
Time Complexity
$O(max(m^{(omega-{2})/(omega-{1})}*n^{2}, n^{({5}*omega-{4})/(omega+{1})})*log^{2}(k/epsilon))$ where omega is the exponent on the complexity of matrix multiplication; currently $O(n^{2.331642})$
Space Complexity
words
()
Description
Approximate?
Approximate
Approximation Factor:
Randomized?
Yes,
Model of Computation
Word RAM
Year
2020