It takes O(n) memory units just to store a list of size n. Why should computers have asymptotically more memory units than processing units? You don’t get to assume an infinitely parallel computer, but O(n)-parallel is only reasonable.
My first impression of the paper is: We can already do this, it’s called an FPGA, and the reason we don’t use them everywhere is that they’re hard to program for.
It takes O(n) memory units just to store a list of size n. Why should computers have asymptotically more memory units than processing units? You don’t get to assume an infinitely parallel computer, but O(n)-parallel is only reasonable.
My first impression of the paper is: We can already do this, it’s called an FPGA, and the reason we don’t use them everywhere is that they’re hard to program for.