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.

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 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

Postscript.

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

Final version

Postscript, PDF (low quality).