Up to Research, Theory group at Nada, KTH.
Computational complexity
Researchers
Alumni
This project is currently inactive.
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.
Old publications
New publication will appear at the participants websites.
- The Shrinkage Exponent is 2
- J. Håstad
- SIAM Journal on Computing, 1998, Vol 27, pp 48-64.
- postscript
-
- 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.
- 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 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
- 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 Read-Once Formulae
- J. Håstad, A. Razborov and A. Yao
- Theoretical computer science, 1995, Vol 141, pp 269-282
- 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 417-426.
-
Up to Research, Theory group at Nada, KTH.
|
