The basic question of efficient computation is to determine the exact computational resources needed to solve a given computational problem. To get an exact answer both upper and lower bounds are needed. Upper bounds are usually proved by displaying an efficient algorithm together with an analysis of its performance. Lower bounds are usually established by mathematical proofs giving an estimate for amount of resources needed. Proving a lower bound implies that one has to prove that any fast algorithm makes a mistake. This quantification over all algorithms seems to make the problem more difficult and progress on lower bounds is very far behind progress on upper bounds.
Our research in this area is mainly concerned with lower bounds in various computational models, but in many cases we also provide upper bounds.
(The descriptive text is from the Theory group's Computational Complexity research page.)
To Research in Computational Complexity, Theory group at Nada, KTH.