If cannot find what you want do not hesitate to contact me by email: username 'johanh' then the at sign followed by domain 'kth.se'.

Journal publications

• J. Håstad, Oneway Permutations in NC0. Information Processing Letters, 1987/88, Vol 26, pp 153-155.
• J. Håstad, Solving Simultaneous Modular Equations of Low Degree, SIAM Journal on Computing, 1988, Vol. 17, No 2, pp 336-341.
• J. Håstad, Dual Vectors and Lower Bounds for the Nearest Lattice Point Problem, Combinatorica, Vol 8, No 1, 1988, pp 75-81.
• J. Håstad, Almost Optimal Lower Bounds for Small Depth Circuits, in Randomness and Computation, Advances in Computing Reasearch, Vol 5, ed. S. Micali, 1989, JAI Press Inc, pp 143-170.
• J. Håstad, Tensorrank is NP-complete, Journal of Algorithms, 1990, Vol 11, pp 644-654.
• W. Aiello, J. Håstad and S. Goldwasser, On the Power of Interaction, Combinatorica, 1990, Vol 10, No 1, pp 3-25.
• J. Håstad and M. Goldmann, On the Power of Small-Depth Threshold Circuits, Computational Complexity, Vol 1, 1991, pp 113-129.
• W. Aiello and J. Håstad, Statistical Zero-Knowledge Languages can be Recognized in Two Rounds, Journal of Computer and System Sciences}, Vol 42, 1991, pp 327-345. Comment.
• W. Aiello and J. Håstad, Relativized Perfect Zero-Knowledge is not BPP, Information and Computation, 1991, Vol 93, No 2, pp 223-240.
• M. Goldmann, J. Håstad and A. Razborov, Majority Gates vs. General Weighted Threshold Gates, Journal of Computation Complexity, 1992, Vol 1, No 4, pp 277-300.
• N. Alon, O. Goldreich, J. Håstad and R. Peralta, Simple Constructions of Almost k-wise Independent Random Variables Random Stuctures and Algorithms, Vol 3, No 3, 1992, pp 289-304. Addendum.
• M. Goldmann and J. Håstad, A Simple Lower Bound for the Depth of Monotone Circuits Computing Clique using a Communication Game, Information Processing Letters, Vol 41, No 4, 1992, pp 221-226.
• J. Håstad, A. Schrift och A. Shamir, The Discrete Logarithm Modulo a Composite Hides O(n) bits, Journal of Computer and System Science, 1993, Vol 47, No 3, pp 376-404.
• J. Håstad and A. Wigderson, Composition of the Universal Relation, in Advances in Computational Complexity Theory, AMS-DIMACS book series, Volume 13, 1993, ed. J-Y Cai.
• J. Håstad, S. Phillips and S. Safra, A Well Characterized Approximation Problem, Information processing letters, Vol 47:6, 1993 pp. 301-305.
• M. Goldmann, P. Grape, and J. Håstad, On Average Time Hierarchies, Information processing letters, Vol 49:1, 1994, pp 15-20.
• R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Håstad, D. Ranjan and P. Rohatgi, The Random Oracle Hypothesis is False, Journal of Computer and System Sciences, Volume 49, No 1, 1994 pp 24-39.
• J. Håstad, I. Wegener, N. Wurm and S. Yi, Optimal Depth, very Small Size Circuit for Symmetric Functions in AC0, Information and Computation, Volume 108, No 2, 1994, pp 200-211.
• J. Håstad, On the Size of Weights for Threshold Gates, SIAM J. on Discrete mathematics}, Vol 7, no 3, 1994, pp 484-492.
• J. Håstad, A. Razborov and A. Yao, On the Shrinkage Exponent of Read-Once Formulae, Theoretical computer science, 1995, Vol 141, pp 269-282.
• J. Håstad, S. Jukna, and P. Pudlak, Top-Down Lower Bounds for Depth 3 Circuits, Computational Complexity, 1995, Vol 5, pp 99-112.
• J. Håstad, T. Leighton and B. Rogoff, Analysis of Backoff Protocols for Multiple Access Channels, \it SIAM Journal on Computing, 1996, Vol 25, pp 740-774.
• L. Cai, J. Chen, and J, Håstad, Circuit Bottom Fan-in and Computational Power, SIAM Journal on Computing, 1998, Vol 27, pp 341-355.
• J. Håstad, The Shrinkage Exponent is 2, SIAM Journal on Computing, 1998, Vol 27, pp 48-64.
• M. Goldmann and J. Håstad, Monotone Circuits for Connectivity have Depth log n to the power (2-o(1)), SIAM Journal on Computing, 1998, vol 27, pp 1283-1294.
• M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan, Linearity Testing in Characteristic Two, IEEE Transactions on Information Theory, Vol 42, No 6, November 1996, pp 1781-1796. Also available, without a figure that causes printing problems on some systems.
• O. Goldreich, J. Håstad, On the complexity of interactive proof with bounded communication, Information processing letters, Vol.~67 (4), 1998, pp 205--214.
• J. Håstad, Clique is Hard to Approximate within n to the power 1-epsilon, Acta Mathematica, Vol 182, 1999, pp 105-142.
• J. Håstad, On bounded occurence constraint satisfaction, Information processing letters, Vol.~74 (1), 2000, pp 1--6.
• J. Håstad, R. Imagliazzo, L. Levin, and M. Luby, A Pseudorandom Generator from any one-way function, SIAM Journal on Computing, Vol 28, 1999, pp 1364--1396.
• A. Andersson, T. Hagerup, J. Håstad and O. Petersson, Tight bounds for searching a sorted array, SIAM Journal on Computing, Vol 30, 2000, pp 1552--1578.
• J. Håstad, Some optimal inapproximability results, Journal of ACM, Vol.~48, 2001, pp 798--859.
• G. Andersson, L. Engebretsen, and J. Håstad, A new way to use semidefinite programming with applications to linear equations mod p, Journal of Algorithms, Vol.~39, 2001, pp 162--204.
• D. Dor, J. Håstad, S. Ulfberg, and U. Zwick, On lower bounds for selecting the median, SIAM Journal on discrete mathematics, Vol.~14, 2001, pp 299--311.
• Y. Aumann, J. Håstad, M. Rabin, and M. Sudan, Linear consistency testing, Journal of Computer and System Sciences, Vol.~62 (1), 2001, pp 589--607.
• J. Håstad, L. Ivansson, and J. Lagergren, Fitting points on the real line and its application to RH-mapping, Journal of Algorithms, Vol 49:1, 2003, pp 42-62.
• J. Håstad, S. Linusson, and J. Wästlund, A smaller sleeping bag for a baby snake, Discrete and Computational Geometry, Vol 26, 2001, pp 173--181.
• J. Håstad, A slight sharpening of LMN, Journal of Computer and System Sciences, Vol 63, 2001, pp 498-508.
• V. Guruswami, J. Håstad, M. Sudan, and D. Zuckerman, Combinatorial bounds for list decoding, IEEE transactions on Information theory, Vol 48, 2002, pp 1021-1034.
• V. Guruswami, J. Håstad, and M. Sudan, Hardness of Approximate Hypergraph Coloring, SIAM Journal on Computing, Vol 31, 2002, pp 1663-1686.
• J. Håstad and A. Wigderson, Simple Analysis of graph tests for linearity and PCP, Random Structures and algorithms, Vol 22, 2003, pp 139-160.
• J. Håstad and M. Näslund, The Security of all RSA and Discrete Log Bits, Journal of the ACM, Vol 51:2, 2004, pp 187-230.
• J. Håstad and V. Srinivasan, On the advantage over a random assignment, Random structures and Algorithms, Vol 25:2, 2004, pp 117-149.
• J. Håstad and S. Khot, Query efficient PCPs with perfect completeness, Theory of Computing, Vol 1, 2005, pp 119-149.
• J. Håstad, The square lattice shuffle, accepted for publication in {\it Random structures and Algorithms}, 2006.

Conference publications

• J. Håstad, J. Jonsson, A. Juels, and M. Yung, Funkspiel schemes. an alternative to conventional tamper resistance, 7th ACM conference on Computer communications security, ACM Press, 2000, pp 125-133.
• J. Håstad and M. Näslund, Practical construction and analysis of pseudo-randomness primitives, Aciacrypt 2001, LNCS 2248, pp 442-459.
• J. Håstad, Every 2-CSP Allows Nontrivial Approximation, Proceedings of the 37th Annual ACM Symposium on Theory of Computation, pp 740--746, Baltimore, May 2005.

Other publications

• J. Håstad, Computational limitations for small depth circuits, a book manuscript based on Ph.D-thesis, 1986.
• J. Håstad and T. Leighton, Division in O(log n) depth using n to the power 1+epsilon processors, manuscript.