Please note that many of the below publications are subject
to copyright restrictions but you are free to use such
publications for personal use. I keep only the most
recent version of each paper in the below list and
thus a conference paper can disappear and come back
in the form of 'unpublished' or 'journal publication'.
Futhermore some of the publications are slightly different
from the published version and in need of an official
version please go to the indicated source.
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 and A. Shamir The Cryptographic
Security of Truncated Linearly related Variables.
17th Annual ACM Symposium on Theory
of Computation, 1985, pp 356--362.
- J. Håstad, Oneway Permutations in NC0.
Information Processing Letters, 1987/88, Vol 26, pp 153-155.
- A. Frieze, J. Håstad, R. Kannan, J. Lagarias
and A. Shamir Reconstructing Truncated Integer Variables Satisfying Linear Congruences, SIAM Journal on Computing, 1988, Vol. 17, No 2,
pp 262--280.
- 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
(pdf).
- 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 (only ps)
IEEE Transactions on Information Theory, Vol 42, No 6, November 1996,
pp 1781-1796. Also
available as pdf, 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,
Random structures and Algorithms, Vol 29, 2006, pp 466-474.
Correction,
- J. Håstad,
The security of the IAPM and IACBC modes,
Journal of Cryptology, Volume 20:2, 2007, pp 153-163
- J. Håstad
On the efficient approximability of constraint satisfaction
problems, in Surveys in Combinatorics 2007, London
Mathematical Society Lecture Notes Series, Vol 346,
eds A. Hilton and J.Talbot, Cambridge University Press, 2007,
pp 201-222.
- J. Håstad and A. Wigderson
The randomized communicatin complexity of set disjointness,
Theory of Computing, Vol 3, 2007, pp 211-219.
- J. Håstad,
Every 2-CSP Allows Nontrivial Approximation,
Computational Complexity, Vol 17, 2008, pp 549-566.
- J. Håstad and M. Näslund,
Practical Construction and Analysis of Pseudo-randomness
Primitives, Journal of Cryptology, Volume 21:1, 2008, pp 1-26.
- J. Håstad,
On the Approximation Resistance of a Random Predicate,
Computational Complexity, Volume 18, 2009, pp 413-434.
- V. Guruswami, J. Håstad, and S. Kopparty,
On the List-Decodability of Random Linear Codes,
IEEE transactions on Information Theory, vol 57, 2011, pp 718-725.
- P. Austrin and J. Håstad,
Randomly supported independence and resistance,
SIAM Journal on Computing, volume 40, 2011, pp 1-27.
- V. Guruswami, J Håstad, R. Manokaran, P. Raghavendra, and M. Charikar,
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant,
SIAM Journal on Computing, volume 40, 2011, pp 878-914.
- M. Cheraghchi, J. Håstad, M. Isaksson and O. Svensson,
Approximating Linear Threshold Predicates,
ACM Transactions on Computation Theory, 2012, Vol 4, pp 1-31.
- P. Austrin and J. Håstad,
On the Usefulness of Predicates,
ACM Transactions on Computation Theory, 2013, Vol 5, pp 1-24.
- J. Nordström and J. Håstad,
Towards an Optimal Separation of Space and Length in Resolution,
Theory of Computing, Vol 9, 2013, pp 471-557.
- J. Håstad,
Satisfying degree-d equations over GF(2)n,
Theory of Computing, Vol 9, 2013, pp 845-862.
- J. Håstad,
On the NP-hardness of Max-Not-2,
SIAM Journal on Computing, Vol 49, 2014, pp 179-193.
- J. Håstad,
On the correlation of parity and small-depth circuits,
SIAM journal on Computing, 2014, Vol 43, pp 1699-1708.
- B. Barak, P. Gopalan, J. Håstad, R. Mekha, P. Raghavendra, and D. Steurer,
Making the Long Code Short,
SIAM journal on Computing, 2015, Vol 44, pp 1287-1324.
- J. Håstad, S. Huang. R. Manokaran, R. O'Donnell, J. Wright
Improved NP-inapproximability for
2-variable linear equations,
Theory of Computing, Vol 13(19), pp 1-51.
- V. Gurusawmi, P. Harsha, J. Håstad, S. Srinivasan, G. Varma
Super-polylogarithmic hypergraph coloring
hardness via low-degree long codes, SIAM Journal on Computing,
2017, Vol 46, 132-159.
- B. Bukh, V. Guruswami, J. Håstad,
An improved bound on the fraction of
correctable deletions,
IEEE Transaction on Information Theory, 2017, Vol 63, 93-103.
- P. Austrin, V. Guruswami, and J. Håstad,
(2+epsilon)-Sat is NP-hard,
Siam Journal on Computing, Vol 46, 2017, pp 1554-1573.
- J. Håstad, B. Rossman, R. Servedio, L-Y. Tan.
An average-case depth hierarchy theorem for higher depths, Journal of the ACM, 2017, Vol 64, pp 1-27.
- J. Håstad, and R. Manokaran,
On the Hardness of Approximating Homogenous 3-Lin,
to appear in Theory of Computing.
- R. Boppana, J. Håstad, C.H. Lee, and E. Viola,
Bounded independence vs symmetric test,
ACM Transactions on Computation
Theory, 2019, Volume 4, Article 21, pp 1-27.
- J. Håstad, G. Lagarde, and J. Swernofsky,
d-Galvin
families, The Electronic Journal of Combinatorics, Volume 27,
Issue 1, 2020, pp 1-36.
- J. Håstad,
On small-depth Frege proofs for Tseitin for grids,
Journal of the ACM, 2020, volume 68, pp 1-31.
- V. Guruswami and J. Håstad,
Explicit two-deletion codes with redundancy matching the existential bound, Transactions on Information theory, 2021, Volume 67, pp 6384-6394.
Some Conference publications lacking journal versions
- B. Chor, J. Friedman, O. Goldreich, J. Håstad,
S. Rudich and R. Smolensky
The Bit Extraction Problem or t-resilient Functions, Proceedings 26th Annual IEEE Symposium of Foundations of
Computer Science, 1985, pp 396--407.
- 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,
Complexity theory, proofs and approximation,
plenary address, Europeand Congress of
Mathematics, editor A.~Laptev, European Mathematical Society,
2005.
- J. Håstad, R. Pass, D. Wikström and K. Pietrzak,
An Efficient Parallel Repetition Theorem,
Theory of Cryptography, Proceedins for 7th Theory of Cryptography Conference,
eds. D. Micciancio, Springer Lecture Notes in Computer Science,
5978, pp 1-18, February 2010.
- P. Austrin, J. Håstad, and Rafael Pass,
On the Power of Many One-Bit Provers,
Proceedings of
the 4th conference on Innovations in Theoretical Computer Science, 2013,
ACM, pp 215-220.
- E. Blais, J. Håstad, R. Servedio, L.-Y. Tan
On
DNF approximators for monotone Boolean functions,
Proceedings of ICALP 2014, pp 235--246.
- M. Ekerå and J. Håstad
Quantum Algorithms for Computing Short Discrete Logarithms
and Factoring RSA Integers ,
Internatinal Workshop on Post-Quantum
Cryptography, PQCrypto 2017, Springer Lecture Notes in Computer
Science, volume 10346.
- P. Austrin, J. Brown-Cohen, and J. Håstad,
Optimal Inapproximability with Universal Factor Graphs,
, proceedings ACM-SIAM
Symposium on Discrete Algorithms 2021, pp 434-453.
- J. Håstad and K. Risse,
Bounded depth proofs for Tseitin formulas on the grid; revisited ,
proceedings of 63rd Annual IEEE Symposium on Foundations of
Computer Science, 2022, pp 1138-1149.
- J. Håstad,
On small-depth Frege proofs for PHP ,
proceedings of 64th Annual IEEE Symposium on Foundations of
Computer Science, 2023.
Other publications
- J. Håstad,
Computational limitations for small depth circuits,
a book manuscript based on Ph.D-thesis, 1986. There are some figures missing
from this file. They can, in primitive form, be found
here, but exists also in the form of a combined,
non-official version, thanks to Shouwei Li.
- J. Håstad and T. Leighton,
Division in O(log n) depth using n to the power
1+epsilon processors, manuscript.
- J. Håstad,
Improved bounds for bounded occurrence constraint
satisfaction, manuscript, 2015.
Responsible for this page: Johan Håstad <johanh@nada.kth.se>
Latest change December 4, 2017
Technical support: <webmaster@nada.kth.se>