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.
Publications
 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
PDF.

 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

PDF.
 Ph. D. Thesis: On Lower Bounds for Circuits and Selection
 Final version

PDF
Staffan Ulfberg <staffan@ulfberg.se>