3 ms·
Prof Aaronson said the best upper bound they have so far is O(log(n)^33)... to give that more meaning, O(log(n)^33) grows faster than O(n) until about n = 10^15
by titanomachy 8y ago
Prof Aaronson said the best upper bound they have so far is O(log(n)^33)... to give that more meaning, O(log(n)^33) grows faster than O(n) until about n = 10^15, so "not practical" is a bit of an understatement!
I still get why this is an interesting result, though. And if Scott thinks that lower bounds are achievable he is probably right.
- paradroid 8y ago10^15 is not that big. We could construct and compute on sparse matrices that large today.
- rspeer 8y agoI'm glad to know where the crossover point is, and yeah, hearing that it's around 10^15 tells me it's just a few orders of magnitude of improvement away from being a practical machine learning tool.