Up to Research, Theory group at Nada, KTH.
Computational complexity
Researchers
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 4864.
 postscript

 Circuit Bottom Fanin and Computational Power
 L. Cai, J. Chen, and J, Håstad
 SIAM Journal on Computing, 1998, Vol 27, pp 341355.
 postscript

 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 115, Springer Verlag.

 On the BPP Hierarchy Problem
 Christer Berg and Johan Håstad
 Technical report TRITANA9702, Royal Institute of Tecnology, 1997
Postscript.

 Monotone Circuits for Connectivity have Depth
(log n)^{2o(1)}
 M. Goldmann and J. Håstad
 Proceedings
of 27th Annual ACM Symposium on Theory of Computation, 1995, pp 569574.

 TopDown Lower Bounds for Depth 3 Circuits
 J. Håstad, S. Jukna, and P. Pudlak
 Computational Complexity, 1995, Vol 5, pp 99112
 postscript

 On lower bounds for selecting the median
 D. Dor, J. Håstad, S. Ulfberg and U. Zwick
 Manuscript 1997

Postscript.
 On the Shrinkage Exponent of ReadOnce Formulae
 J. Håstad, A. Razborov and A. Yao
 Theoretical computer science, 1995, Vol 141, pp 269282
 Postscript

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

Up to Research, Theory group at Nada, KTH.
Responsible for this page: Johan Håstad <johanh@nada.kth.se>
Latest change January 12, 1999
Technical support: <webmaster@nada.kth.se>