Peng, Vempala (Sparse Linear system of equations)
Revision as of 11:54, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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 == Reference == https://arxiv.org/abs/2007.10254")
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