This is Pierre Lairez' talk "What is ... the complexity of matrix multiplication?" at the "What is ...?" seminar. The talk was given on Friday, April 24, 2015, 1:00pm at the BMS Loft at Urania.
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.
For more "What is ...?" seminar videos, visit math.fu-berlin.de/w/Math/WhatIsSeminar.