Major unsolved problems in theoretical computer science? Wikipedia only lists two problems under "unsolved problems in computer science":


P = NP?
The existence of one-way functions


What are other major problems that should be added to this list?

Rules:


Only one problem per answer
Provide a brief description and any relevant links
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).