What is the lowest known complexity for multiplication?

[CRGreathouse]

'Schoolbook' multiplication takes O(n^2) operations. Karatsuba multiplication takes O(n^{\lg 3})\approx O(n^{1.59}) operations. The best method I know of (which is only practical for very large numbers) is O(n \log n \log\log n).

Is there a known nontrivial lower bound on the complexity of multiplication? I read a paper that discussed the time-(silicon) area tradeoff on multiplication, but I wasn't able to get a useful bound from that (caring only about the time and not knowing how to 'remove' the area):
The Area-Time Complexity of Binary Multiplication

Can anyone help me out here?

 

[chronon]

Well Donald Knuth's The Art of Computer Programming, Volume 2: Seminumerical Algorithms has a chapter entitled How fast can we multiply and if I remember correctly he comments on the lack of a lower bound for multiplication algorithms. However, that was written over 35 years ago, so you'd think that there'd have been some progress since then. I tried searching for papers with references to that chapter of Knuth's book, but didn't find very many of them.

 

[CRGreathouse]

Yeah, I've been searching but haven't found anything. I hoped the new Algorithms by Dasgupta, Papadimitriou, and Vazirani might have something, but no such luck. I don't have a copy of Knuth's book or that's where I would have started (old as it is).

I did find something online, but I don't think I trust it: "Surprisingly, there are several better [multiplication] algorithms, taking as few as n\log n operations (although whether it's possible to solve this in O(n) operations is a major open problem)."
http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec1.pdf
What do you think? On one hand it supports what you remember reading; on the other, it's written for a basic audience and (seems to) misquote the complexity of (what I presume to be) S-S multiplication.

 

[chronon]

No, I don't believe the n log n claim either. I did find http://www.csc.liv.ac.uk/~ped/teachadmin/algor/complex.html which reports it as a conjecture, but even then I'm doubtful - I would have thought that an n log n algorithm would be straightforward enough to have been found by now. It looks like S-S is still the optimum. The lack of a good lower bound isn't particularly surprising, proving such things is never easy.