Pierre Lairez (TU Berlin)

2015/04/24, 13:00

Urania Berlin, at BMS Loft (3rd floor)

Studies in computer algebra led to numerous efficient algorithms to solve many kinds of difficult problems (e.g., large integer multiplication). Complexity theory focuses on problems for which an efficient solution is not known and tries to grasp the intrinsic difficulty of problems. This involves both searching for lower bounds and upper bounds. Matrix multiplication is one of these hard problems. The obvious algorithm needs $n^3$ scalar multiplications to multiply two n by n matrices, and it is far from optimal. Simple methods and sophisticated tools allow to lower this bound, but it seems likely that we are still not close to optimal.