Staffan Ulfberg's Research

Computational Complexity

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.


Master Thesis: Computational Aspects of a Stochastic Metapopulation Model
Staffan Ulfberg Postscript, PDF.
Symmetric Approximation Arguments for Monotone Lower Bounds without Sunflowers
Christer Berg and Staffan Ulfberg
Computational Complexity, vol 8, no. 1 Postscript.
A Lower Bound for Perceptrons and an Oracle Separation of the PP^PH Hierarchy
Christer Berg and Staffan Ulfberg
Conference version in Proceedings, Computational Complexity 97
To appear in Journal of Computer and System Sciences Postscript.
On lower bounds for selecting the median
D. Dor, J. Håstad, S. Ulfberg and U. Zwick
SIAM Journal of Discrete Mathematics, vol 14, no. 3
Ph. D. Thesis: On Lower Bounds for Circuits and Selection
Final version
Postscript, PDF (low quality).

Staffan Ulfberg <>