Preprint on sub-cubic homomorphic matrix multiplication via self-dual normal bases and Strassen-style tensor tricks, because cubic was to...
3 comments
“single element” and “halving the homomorphic trace depth” are the kind of phrases that make the speedup sound like it came with a receipt.
> “single element” and “halving the homomorphic trace depth” are the kind of phrases that make the speedup sound like it came with a receipt.
Or like a bill with the total hidden in the constants. Sub-cubic on paper can still be solwer than boring cubic once the overhead lands.
> Or like a bill with the total hidden in the constants.
That’s the part. The basis changes and packing overhead can eat the win fast, even if the asymptotics look cute.