^ Up to Research, Theory group at Nada, KTH.

Computational complexity


Ph.D. students

Short description

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 bound 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 algorithm 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.

Recent publications

The Shrinkage Exponent is 2
J. Håstad
SIAM Journal on Computing, 1998, Vol 27, pp 48-64.
Circuit Bottom Fan-in and Computational Power
L. Cai, J. Chen, and J, Håstad
SIAM Journal on Computing, 1998, Vol 27, pp 341-355.
Symmetric Approximation Arguments for Monotone Lower Bounds without Sunflowers
Christer Berg and Staffan Ulfberg
To appear in the journal Computational Complexity 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.
The Complexity of Computing Hard Core Predicates
M. Goldmann and M. Näslund
Proceedings, CRYPT0 '97. LNCS 1294, pp 1-15, Springer Verlag.
On the BPP Hierarchy Problem
Christer Berg and Johan Håstad
Technical report TRITA-NA-9702, Royal Institute of Tecnology, 1997 Postscript.
Monotone Circuits for Connectivity have Depth (log n)^{2-o(1)}
M. Goldmann and J. Håstad
Proceedings of 27th Annual ACM Symposium on Theory of Computation, 1995, pp 569-574.
Top-Down Lower Bounds for Depth 3 Circuits
J. Håstad, S. Jukna, and P. Pudlak
Computational Complexity, 1995, Vol 5, pp 99-112
On lower bounds for selecting the median
D. Dor, J. Håstad, S. Ulfberg and U. Zwick
Manuscript 1997
On the Shrinkage Exponent of Read-Once Formulae
J. Håstad, A. Razborov and A. Yao
Theoretical computer science, 1995, Vol 141, pp 269-282
A Tight Lower Bound for Searching a Sorted Array
A. Andersson, J. Håstad and O. Petersson,
Proceedings of 27th Annual ACM Symposium on Theory of Computation, 1995, pp 417-426.

^ Up to Research, Theory group at Nada, KTH.

Responsible for this page: Johan Håstad <>
Latest change January 12, 1999
Technical support: <>