Johan Hastad - Selected 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.
• 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, pp 1-31.
• 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. Nordström and J. Håstad, Towards an Optimal Separation of Space and Length in Resolution, fairly complete version, official version in Proceedings of the 37th Annual ACM Symposium on Theory of Computation, pp 701--710, Victoria, British Columbia, May 2008.
• 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.
• J. Håstad, Satisfying degree-d equations of GF(2)n, draft of full version, preliminary version in Proceedings of APPROX 2011, Princeton. Springer Lecture Notes in Computer Science, Vol 6845, 2011, pp 242-253.
• J. Håstad, On the NP-hardness of Max-Not-2, draft of full version, preliminary version to appear at Approx, 2012.
• P. Austrin and J. Håstad, On the Usefulness of Predicates, draft of full version, preliminary version to appear at Computational Complexity, 2012.
• 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.