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>