6 ms·

> “Philosophically we didn’t know before if you can go faster than matrix multiplication,” said Vempala. > Now we do. This is the part of computer science tha

by mabbo 6y ago

> “Philosophically we didn’t know before if you can go faster than matrix multiplication,” said Vempala. > Now we do. This is the part of computer science that I love. It's a branch of philosophy about what is possible with computing machines. Now all that's left is the matter of making this practical.

eru 6y ago
You might like Scott Aaronson's 'Why Philosophers Should Care About Computational Complexity' https://www.scottaaronson.com/papers/philos.pdf https://www.scottaaronson.com/papers/philos.pdf
- JonathanMerklin 6y ago
  If this paper whets your appetite (talking mostly to grandparent comment, but also HN at large) OR alternatively if you think that this paper is a bit too advanced for your knowledge level, I implore you to read Scott Aaronson's book "Quantum Computing Since Democritus". The book is one of the finest in the genre of "too casual to be a textbook, too informative to be an easy read for laymen" nonfiction, and it is primarily concerned with philosophy vis-à-vis computational complexity. It does a pretty good job at assuming you only have a bit of computer science background (pun unintended, noticed, left in) and builds your knowledge base up from introductory set theory and first order logic in the earliest pages (In fact, it's based on a course he taught, and his lecture notes are available online and frequently make for fantastic supplemental material [1]). One of my favorite reads of 2020. [1] https://www.scottaaronson.com/democritus/ https://www.scottaaronson.com/democritus/
  - spockz 6y ago
    Thank you for showing it is “to whet your appetite”. I always thought it was “to wet your appetite”, which made no sense at all. This is the first time I’d read this phrase instead of heard it spoken.
    - thom 6y ago
      Same as ‘whetstone’, if that helps remember. You’re sharpening/increasing your appetite.
    - magicalhippo 6y ago
      First time I've seen it written like that. I did not know it should be "whet" rather than "wet". > which made no sense at all The way I made some kind of sense of it was as a variation of making your mouth water. But yeah "whet" makes a lot more sense now.
killjoywashere 6y ago
"This relationship can be checked experimentally..." Einstein, 1905
Fordec 6y ago
I'm super 100% out of my depth on this on the math side of things, so bear with me. But isn't matrix multiplication one of the core basis assumptions of GPU based computing architectures, in particular for AI? That doing math in parallel (which matrices fit into like a glove) gets the fastest result? Does this imply that a new future architecture could be, at least in theory, get the natural advantage over what we have at the moment? Because if the answer is yes or even a "possibly, too early to tell, requires more R&D", then the existing GPU manufacturers suddenly have a long term problem and we're very likely about to see a decade of a new arms race in computing architecture.
- cambalache 6y ago
  You are confusing the efficiency of an algorithm with its implementation. Worth repeating the famous Dijkstra's dictum here : “Computer Science is no more about computers than astronomy is about telescopes.”
  - Fordec 6y ago
    I don't believe I am confused actually. I get this is just an algorithm hypothetical being answered right now. I just care about the telescopes way more than the astronomy and am thinking steps ahead about the meta game of the telescope market. Just as I personally would care far more about the real world implications of P=NP far more than the act of solving it.
    - gtr32x 6y ago
      I understand that the answer is no here. Because this method is only suitable for the class of linear system thats the equivalent of sparse matrices. GPUs on the other hand are more optimized for the general purpose matrix multiplication here. Unless it can be shown that there are certain economically high-usage scenarios of this class of problems (e.g. the usage magnitude of bitcoin mining), the investment into this specific research does not seem warranted.
      - 6y ago
ianbooker 6y ago
This part of CS is indeed more a Geisteswissenschaft ("science of the mind"). I think what is most fascinating when you compare it to more conventional philosophy is the fact that you can quantify your advances so easily and precise.
thomasahle 6y ago
>> “Philosophically we didn’t know before if you can go faster than matrix multiplication,” said Vempala. >> Now we do. > This is the part of computer science that I love. It's a branch of philosophy about what is possible with computing machines. Strictly speaking, if w=2 then their bound of n^{(5 w - 4)/(w + 1)} won't be better than n^w. Since we can't rule out w=2 we still don't know for sure that solving sparse systems is strictly easier. However this is a good indication.

by mabbo 6y ago

eru 6y ago

You might like Scott Aaronson's 'Why Philosophers Should Care About Computational Complexity' https://www.scottaaronson.com/papers/philos.pdf https://www.scottaaronson.com/papers/philos.pdf

JonathanMerklin 6y ago
If this paper whets your appetite (talking mostly to grandparent comment, but also HN at large) OR alternatively if you think that this paper is a bit too advanced for your knowledge level, I implore you to read Scott Aaronson's book "Quantum Computing Since Democritus". The book is one of the finest in the genre of "too casual to be a textbook, too informative to be an easy read for laymen" nonfiction, and it is primarily concerned with philosophy vis-à-vis computational complexity. It does a pretty good job at assuming you only have a bit of computer science background (pun unintended, noticed, left in) and builds your knowledge base up from introductory set theory and first order logic in the earliest pages (In fact, it's based on a course he taught, and his lecture notes are available online and frequently make for fantastic supplemental material [1]). One of my favorite reads of 2020. [1] https://www.scottaaronson.com/democritus/ https://www.scottaaronson.com/democritus/
- spockz 6y ago
  Thank you for showing it is “to whet your appetite”. I always thought it was “to wet your appetite”, which made no sense at all. This is the first time I’d read this phrase instead of heard it spoken.
  - thom 6y ago
    Same as ‘whetstone’, if that helps remember. You’re sharpening/increasing your appetite.
  - magicalhippo 6y ago
    First time I've seen it written like that. I did not know it should be "whet" rather than "wet". > which made no sense at all The way I made some kind of sense of it was as a variation of making your mouth water. But yeah "whet" makes a lot more sense now.

killjoywashere 6y ago

"This relationship can be checked experimentally..." Einstein, 1905

Fordec 6y ago

I'm super 100% out of my depth on this on the math side of things, so bear with me. But isn't matrix multiplication one of the core basis assumptions of GPU based computing architectures, in particular for AI? That doing math in parallel (which matrices fit into like a glove) gets the fastest result? Does this imply that a new future architecture could be, at least in theory, get the natural advantage over what we have at the moment? Because if the answer is yes or even a "possibly, too early to tell, requires more R&D", then the existing GPU manufacturers suddenly have a long term problem and we're very likely about to see a decade of a new arms race in computing architecture.

cambalache 6y ago
You are confusing the efficiency of an algorithm with its implementation. Worth repeating the famous Dijkstra's dictum here : “Computer Science is no more about computers than astronomy is about telescopes.”
- Fordec 6y ago
  I don't believe I am confused actually. I get this is just an algorithm hypothetical being answered right now. I just care about the telescopes way more than the astronomy and am thinking steps ahead about the meta game of the telescope market. Just as I personally would care far more about the real world implications of P=NP far more than the act of solving it.
  - gtr32x 6y ago
    I understand that the answer is no here. Because this method is only suitable for the class of linear system thats the equivalent of sparse matrices. GPUs on the other hand are more optimized for the general purpose matrix multiplication here. Unless it can be shown that there are certain economically high-usage scenarios of this class of problems (e.g. the usage magnitude of bitcoin mining), the investment into this specific research does not seem warranted.
    - 6y ago

ianbooker 6y ago

This part of CS is indeed more a Geisteswissenschaft ("science of the mind"). I think what is most fascinating when you compare it to more conventional philosophy is the fact that you can quantify your advances so easily and precise.

thomasahle 6y ago

>> “Philosophically we didn’t know before if you can go faster than matrix multiplication,” said Vempala. >> Now we do. > This is the part of computer science that I love. It's a branch of philosophy about what is possible with computing machines. Strictly speaking, if w=2 then their bound of n^{(5 w - 4)/(w + 1)} won't be better than n^w. Since we can't rule out w=2 we still don't know for sure that solving sparse systems is strictly easier. However this is a good indication.