Major unsolved problems in theoretical computer science?
Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?


The exponent of the best known upper bound even has a special symbol, $\omega$. Currently $\omega$ is approximately 2.376, by the Coppersmith-Winograd algorithm.  A nice overview of the state of the art is Sara Robinson, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38(9), 2005.

Update: Andrew Stothers (in his 2010 thesis) showed that $\omega &lt; 2.3737$, which was improved by Virginia Vassilevska Williams (in a July 2014 preprint) to $\omega &lt; 2.372873$.  These bounds were both obtained by a careful analysis of the basic Coppersmith-Winograd technique.

Further Update (Jan 30, 2014): François Le Gall has proved that $\omega &lt; 2.3728639$ in a paper published in ISSAC 2014 (arXiv preprint).