default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJohan Håstad
Person information
- affiliation: Royal Institute of Technology, Stockholm, Sweden
- award (2018): Knuth Prize
- award (1994,2011): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c71]Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný:
A Logarithmic Approximation of Linearly-Ordered Colourings. APPROX/RANDOM 2024: 7:1-7:6- [i34]Johan Håstad:
On Small-depth Frege Proofs for PHP. CoRR abs/2401.15683 (2024) - [i33]Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný:
A logarithmic approximation of linearly-ordered colourings. CoRR abs/2404.19556 (2024) - 2023
- [j79]Johan Håstad:
The EATCS Award 2023 - Laudatio for Amos Fiat. Bull. EATCS 140 (2023) - [c70]Johan Håstad:
On small-depth Frege proofs for PHP. FOCS 2023: 37-49 - [i32]Johan Håstad:
On small-depth Frege proofs for PHP. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j78]Johan Håstad:
The EATCS Award 2023 - Call for Nominations. Bull. EATCS 138 (2022) - [c69]Johan Håstad, Kilian Risse
:
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. FOCS 2022: 1138-1149 - [i31]Johan Håstad, Kilian Risse:
On bounded depth proofs for Tseitin formulas on the grid; revisited. CoRR abs/2209.05839 (2022) - 2021
- [j77]Johan Håstad:
On Small-depth Frege Proofs for Tseitin for Grids. J. ACM 68(1): 1:1-1:31 (2021) - [j76]Venkatesan Guruswami, Johan Håstad:
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. IEEE Trans. Inf. Theory 67(10): 6384-6394 (2021) - [c68]Venkatesan Guruswami, Johan Håstad:
Explicit two-deletion codes with redundancy matching the existential bound. SODA 2021: 21-32 - [c67]Per Austrin, Jonah Brown-Cohen, Johan Håstad:
Optimal Inapproximability with Universal Factor Graphs. SODA 2021: 434-453 - 2020
- [j75]Johan Håstad, Guillaume Lagarde, Joseph Swernofsky:
d-Galvin Families. Electron. J. Comb. 27(1): 1 (2020) - [j74]Marta Kwiatkowska, Éva Tardos, Johan Håstad:
The EATCS Award 2021 - Call for Nominations. Bull. EATCS 132 (2020) - [i30]Venkatesan Guruswami, Johan Håstad:
Explicit two-deletion codes with redundancy matching the existential bound. CoRR abs/2007.10592 (2020)
2010 – 2019
- 2019
- [j73]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence versus Symmetric Tests. ACM Trans. Comput. Theory 11(4): 21:1-21:27 (2019) - [p1]Johan Håstad:
Following a tangent of proofs. Providing Sound Foundations for Cryptography 2019: 599-622 - [i29]Per Austrin, Jonah Brown-Cohen, Johan Håstad:
Optimal Inapproximability with Universal Factor Graphs. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c66]Johan Håstad:
Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. FOCS 2018: 602 - 2017
- [j72]Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM 64(5): 35:1-35:27 (2017) - [j71]Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes. SIAM J. Comput. 46(1): 132-159 (2017) - [j70]Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-Sat Is NP-hard. SIAM J. Comput. 46(5): 1554-1573 (2017) - [j69]Boris Bukh, Venkatesan Guruswami, Johan Håstad:
An Improved Bound on the Fraction of Correctable Deletions. IEEE Trans. Inf. Theory 63(1): 93-103 (2017) - [j68]Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright:
Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. 13(1): 1-51 (2017) - [j67]Johan Håstad, Rajsekar Manokaran:
On the Hardness of Approximating Balanced Homogenous 3-Lin. Theory Comput. 13(1): 1-19 (2017) - [c65]Johan Håstad:
On Small-Depth Frege Proofs for Tseitin for Grids. FOCS 2017: 97-108 - [c64]Martin Ekerå, Johan Håstad:
Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. PQCrypto 2017: 347-363 - [i28]Martin Ekerå, Johan Håstad:
Quantum algorithms for computing short discrete logarithms and factoring RSA integers. CoRR abs/1702.00249 (2017) - [i27]Johan Håstad:
On small-depth Frege proofs for Tseitin for grids. Electron. Colloquium Comput. Complex. TR17 (2017) - [i26]Martin Ekerå, Johan Håstad:
Quantum algorithms for computing short discrete logarithms and factoring RSA integers. IACR Cryptol. ePrint Arch. 2017: 77 (2017) - 2016
- [j66]Johan Håstad:
The square lattice shuffle, correction. Random Struct. Algorithms 48(1): 213 (2016) - [c63]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence vs. Moduli. APPROX-RANDOM 2016: 24:1-24:9 - [c62]Johan Håstad:
An Average-Case Depth Hierarchy Theorem for Higher Depth. FOCS 2016: 79-88 - [i25]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded independence vs. moduli. Electron. Colloquium Comput. Complex. TR16 (2016) - [i24]Johan Håstad:
An average-case depth hierarchy theorem for higher depth. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j65]Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer:
Making the Long Code Shorter. SIAM J. Comput. 44(5): 1287-1324 (2015) - [c61]Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright:
Improved NP-Inapproximability for 2-Variable Linear Equations. APPROX-RANDOM 2015: 341-360 - 2014
- [j64]Johan Håstad:
On the NP-Hardness of Max-Not-2. SIAM J. Comput. 43(1): 179-193 (2014) - [j63]Johan Håstad, Bettina Just, J. C. Lagarias, Claus-Peter Schnorr:
Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. SIAM J. Comput. 43(1): 254 (2014) - [j62]Johan Håstad:
On the Correlation of Parity and Small-Depth Circuits. SIAM J. Comput. 43(5): 1699-1708 (2014) - [c60]Per Austrin, Johan Håstad, Venkatesan Guruswami:
(2 + epsilon)-Sat Is NP-Hard. FOCS 2014: 1-10 - [c59]Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan:
On DNF Approximators for Monotone Boolean Functions. ICALP (1) 2014: 235-246 - [c58]Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. STOC 2014: 614-623 - 2013
- [j61]Jakob Nordström, Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution. Theory Comput. 9: 471-557 (2013) - [j60]Johan Håstad:
Satisfying Degree-d Equations over GF[2]n. Theory Comput. 9: 845-862 (2013) - [j59]Per Austrin, Johan Håstad:
On the usefulness of predicates. ACM Trans. Comput. Theory 5(1): 1:1-1:24 (2013) - [c57]Per Austrin, Johan Håstad, Rafael Pass:
On the power of many one-bit provers. ITCS 2013: 215-220 - [i23]Per Austrin, Johan Håstad, Rafael Pass:
On the Power of Many One-Bit Provers. CoRR abs/1301.2729 (2013) - [i22]Venkatesan Guruswami, Johan Håstad, Prahladh Harsha, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. CoRR abs/1311.7407 (2013) - [i21]Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-SAT is NP-hard. Electron. Colloquium Comput. Complex. TR13 (2013) - [i20]Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j58]Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson:
Approximating Linear Threshold Predicates. ACM Trans. Comput. Theory 4(1): 2:1-2:31 (2012) - [c56]Johan Håstad:
On the NP-Hardness of Max-Not-2. APPROX-RANDOM 2012: 170-181 - [c55]Per Austrin, Johan Håstad:
On the Usefulness of Predicates. CCC 2012: 53-63 - [c54]Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer:
Making the Long Code Shorter. FOCS 2012: 370-379 - [i19]Per Austrin, Johan Håstad:
On the Usefulness of Predicates. CoRR abs/1204.5662 (2012) - [i18]Johan Håstad, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). Dagstuhl Reports 2(11): 1-19 (2012) - [i17]Johan Håstad:
On the correlation of parity and small-depth circuits. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j57]Per Austrin, Johan Håstad:
Randomly Supported Independence and Resistance. SIAM J. Comput. 40(1): 1-27 (2011) - [j56]Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40(3): 878-914 (2011) - [j55]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. IEEE Trans. Inf. Theory 57(2): 718-725 (2011) - [c53]Johan Håstad:
Satisfying Degree-d Equations over GF[2] n. APPROX-RANDOM 2011: 242-253 - [i16]Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer:
Making the long code shorter, with applications to the Unique Games Conjecture. CoRR abs/1111.0405 (2011) - [i15]Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer:
Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. TR11 (2011) - [i14]Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j54]Johan Håstad:
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. Comput. Complex. 19(2): 151-152 (2010) - [c52]Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson:
Approximating Linear Threshold Predicates. APPROX-RANDOM 2010: 110-123 - [c51]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the list-decodability of random linear codes. STOC 2010: 409-416 - [c50]Johan Håstad, Rafael Pass, Douglas Wikström, Krzysztof Pietrzak:
An Efficient Parallel Repetition Theorem. TCC 2010: 1-18 - [i13]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. CoRR abs/1001.1386 (2010) - [i12]Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson:
Approximating Linear Threshold Predicates. Electron. Colloquium Comput. Complex. TR10 (2010) - [i11]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j53]Johan Håstad:
On the Approximation Resistance of a Random Predicate. Comput. Complex. 18(3): 413-434 (2009) - [c49]Per Austrin, Johan Håstad:
Randomly supported independence and resistance. STOC 2009: 483-492 - 2008
- [j52]Johan Håstad:
Every 2-csp Allows Nontrivial Approximation. Comput. Complex. 17(4): 549-566 (2008) - [j51]Johan Håstad, Mats Näslund:
Practical Construction and Analysis of Pseudo-Randomness Primitives. J. Cryptol. 21(1): 1-26 (2008) - [c48]Jakob Nordström, Johan Håstad:
Towards an optimal separation of space and length in resolution. STOC 2008: 701-710 - [i10]Jakob Nordström, Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution. CoRR abs/0803.0661 (2008) - [i9]Jakob Nordström, Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j50]Johan Håstad, Svante Linusson, Johan Wästlund:
A Smaller Sleeping Bag for a Baby Snake. Discret. Comput. Geom. 38(1): 171 (2007) - [j49]Johan Håstad:
The Security of the IAPM and IACBC Modes. J. Cryptol. 20(2): 153-163 (2007) - [j48]Johan Håstad, Avi Wigderson:
The Randomized Communication Complexity of Set Disjointness. Theory Comput. 3(1): 211-219 (2007) - [c47]Johan Håstad:
On the Approximation Resistance of a Random Predicate. APPROX-RANDOM 2007: 149-163 - 2006
- [j47]Johan Håstad:
The square lattice shuffle. Random Struct. Algorithms 29(4): 466-474 (2006) - [c46]Johan Håstad:
On Nontrivial Approximation of CSPs. APPROX-RANDOM 2006: 1 - 2005
- [j46]Johan Håstad, Subhash Khot:
Query Efficient PCPs with Perfect Completeness. Theory Comput. 1(1): 119-148 (2005) - [c45]Johan Håstad:
Every 2-CSP allows nontrivial approximation. STOC 2005: 740-746 - 2004
- [j45]Johan Håstad, Mats Näslund:
The security of all RSA and discrete log bits. J. ACM 51(2): 187-230 (2004) - [j44]Johan Håstad, Srinivasan Venkatesh:
On the advantage over a random assignment. Random Struct. Algorithms 25(2): 117-149 (2004) - [c44]Yevgeniy Dodis, Rosario Gennaro, Johan Håstad, Hugo Krawczyk, Tal Rabin:
Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. CRYPTO 2004: 494-510 - 2003
- [j43]Johan Håstad, Lars Ivansson, Jens Lagergren:
Fitting points on the real line and its application to RH mapping. J. Algorithms 49(1): 42-62 (2003) - [j42]Johan Håstad, Avi Wigderson:
Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22(2): 139-160 (2003) - [c43]Johan Håstad:
Inapproximability Some history and some open problems. CCC 2003: 265- - 2002
- [j41]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002) - [j40]Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman:
Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory 48(5): 1021-1034 (2002) - [c42]Johan Håstad, Srinivasan Venkatesh:
On the advantage over a random assignment. STOC 2002: 43-52 - 2001
- [j39]Johan Håstad, Svante Linusson, Johan Wästlund:
A Smaller Sleeping Bag for a Baby Snake. Discret. Comput. Geom. 26(1): 173-181 (2001) - [j38]Johan Håstad:
Some optimal inapproximability results. J. ACM 48(4): 798-859 (2001) - [j37]Gunnar Andersson, Lars Engebretsen, Johan Håstad:
A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p. J. Algorithms 39(2): 162-204 (2001) - [j36]Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear-Consistency Testing. J. Comput. Syst. Sci. 62(4): 589-607 (2001) - [j35]Johan Håstad:
A Slight Sharpening of LMN. J. Comput. Syst. Sci. 63(3): 498-508 (2001) - [j34]Dorit Dor, Johan Håstad, Staffan Ulfberg, Uri Zwick:
On Lower Bounds for Selecting the Median. SIAM J. Discret. Math. 14(3): 299-311 (2001) - [c41]Johan Håstad, Mats Näslund:
Practical Construction and Analysis of Pseudo-Randomness Primitives. ASIACRYPT 2001: 442-459 - [c40]Johan Håstad, Avi Wigderson:
Simple Analysis of Graph Tests for Linearity and PCP. CCC 2001: 244-254 - [c39]Johan Håstad, Subhash Khot:
Query Efficient PCPs with Perfect Completeness. FOCS 2001: 610-619 - 2000
- [j33]Johan Håstad:
On bounded occurrence constraint satisfaction. Inf. Process. Lett. 74(1-2): 1-6 (2000) - [j32]Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson:
Tight Bounds for Searching a Sorted Array of Strings. SIAM J. Comput. 30(5): 1552-1578 (2000) - [c38]Johan Håstad, Jakob Jonsson, Ari Juels, Moti Yung:
Funkspiel schemes: an alternative to conventional tamper resistance. CCS 2000: 125-133 - [c37]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158 - [c36]Johan Håstad:
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? ICALP 2000: 235 - [i8]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of approximate hypergraph coloring. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j31]Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby:
A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4): 1364-1396 (1999) - [c35]Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. RANDOM-APPROX 1999: 109-120 - [c34]Gunnar Andersson, Lars Engebretsen, Johan Håstad:
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p. SODA 1999: 41-50 - [i7]Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. Electron. Colloquium Comput. Complex. TR99 (1999) - [i6]Johan Håstad, Mats Näslund:
The Security of all RSA and Discrete Log Bits. Electron. Colloquium Comput. Complex. TR99 (1999) - [i5]Johan Håstad:
On approximating CSP-B. Electron. Colloquium Comput. Complex. TR99 (1999) - [i4]Johan Håstad, Mats Näslund:
Security of all RSA and Discrete Log Bits. IACR Cryptol. ePrint Arch. 1999: 19 (1999) - 1998
- [j30]Oded Goldreich, Johan Håstad:
On the Complexity of Interactive Proofs with Bounded Communication. Inf. Process. Lett. 67(4): 205-214 (1998) - [j29]Johan Håstad:
The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput. 27(1): 48-64 (1998) - [j28]Liming Cai, Jianer Chen, Johan Håstad:
Circuit Bottom Fan-In and Computational Power. SIAM J. Comput. 27(2): 341-355 (1998) - [j27]Mikael Goldmann, Johan Håstad:
Monotone Circuits for Connectivity Have Depth (log n)2-o(1). SIAM J. Comput. 27(5): 1283-1294 (1998) - [c33]Johan Håstad, Lars Ivansson, Jens Lagergren:
Fitting Points on the Real Line and Its Application to RH Mapping. ESA 1998: 465-476 - [c32]Johan Håstad, Mats Näslund:
The Security of Individual RSA Bits. FOCS 1998: 510-521 - [c31]Johan Håstad:
Some Recent Strong Inapproximability Results. SWAT 1998: 205-209 - 1997
- [c30]Liming Cai, Jianer Chen, Johan Håstad:
Circuit Bottom Fan-in and Computational Power. CCC 1997: 158-164 - [c29]Johan Håstad:
Some Optimal Inapproximability Results. STOC 1997: 1-10 - [i3]Johan Håstad:
Some optimal inapproximability results. Electron. Colloquium Comput. Complex. TR97 (1997) - [i2]Johan Håstad:
Clique is hard to approximate within n1-epsilon. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j26]Johan Håstad, Frank Thomson Leighton, Brian Rogoff:
Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput. 25(4): 740-774 (1996) - [j25]Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan:
Linearity testing in characteristic two. IEEE Trans. Inf. Theory 42(6): 1781-1795 (1996) - [c28]Johan Håstad:
Clique is Hard to Approximate Within n1-epsilon. FOCS 1996: 627-636 - [c27]Johan Håstad:
Testing of the Long Code and Hardness for Clique. STOC 1996: 11-19 - [i1]Oded Goldreich, Johan Håstad:
On the Message Complexity of Interactive Proof Systems. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [j24]Johan Håstad, Stasys Jukna, Pavel Pudlák:
Top-Down Lower Bounds for Depth-Three Circuits. Comput. Complex. 5(2): 99-112 (1995) - [j23]Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao:
On the Shrinkage Exponent for Read-Once Formulae. Theor. Comput. Sci. 141(1&2): 269-282 (1995) - [c26]Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan:
Linearity Testing in Characteristic Two. FOCS 1995: 432-441 - [c25]Arne Andersson, Johan Håstad, Ola Petersson:
A tight lower bound for searching a sorted array. STOC 1995: 417-426 - [c24]Mikael Goldmann, Johan Håstad:
Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract). STOC 1995: 569-574 - 1994
- [j22]Johan Håstad, Ingo Wegener, Norbert Wurm, Sang-Zin Yi:
Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC0. Inf. Comput. 108(2): 200-211 (1994) - [j21]Mikael Goldmann, Per Grape, Johan Håstad:
On Average Time Hierarchies. Inf. Process. Lett. 49(1): 15-20 (1994) - [j20]Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi:
The Random Oracle Hypothesis Is False. J. Comput. Syst. Sci. 49(1): 24-39 (1994) - [j19]Johan Håstad:
On the Size of Weights for Threshold Gates. SIAM J. Discret. Math. 7(3): 484-492 (1994) - [c23]Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson:
The complexity of searching a sorted array of strings. STOC 1994: 317-325 - [c22]Johan Håstad:
Recent Results in Hardness of Approximation. SWAT 1994: 231-239 - 1993
- [j18]Johan Håstad, Steven J. Phillips, Shmuel Safra:
A Well-Characterized Approximation Problem. Inf. Process. Lett. 47(6): 301-305 (1993) - [j17]Johan Håstad, A. W. Schrift, Adi Shamir:
The Discrete Logarithm Modulo a Composite Hides O(n) Bits. J. Comput. Syst. Sci. 47(3): 376-404 (1993) - [j16]Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Addendum to "Simple Construction of Almost k-wise Independent Random Variables". Random Struct. Algorithms 4(1): 119-120 (1993) - [c21]Johan Håstad:
The shrinkage exponent is 2. FOCS 1993: 114-123 - [c20]Johan Håstad, Stasys Jukna, Pavel Pudlák:
Top-Down Lower Bounds for Depth 3 Circuits. FOCS 1993: 124-129 - [c19]Johan Håstad, Steven J. Phillips, Shmuel Safra:
A Well-Characterized Approximation Problem. ISTCS 1993: 261-265 - 1992
- [j15]Mikael Goldmann, Johan Håstad, Alexander A. Razborov:
Majority Gates VS. General Weighted Threshold Gates. Comput. Complex. 2: 277-300 (1992) - [j14]Mikael Goldmann, Johan Håstad:
A Simple Lower Bound for Monotone Clique Using a Communication Game. Inf. Process. Lett. 41(4): 221-226 (1992) - [j13]Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Simple Construction of Almost k-wise Independent Random Variables. Random Struct. Algorithms 3(3): 289-304 (1992) - [c18]Mikael Goldmann, Johan Håstad, Alexander A. Razborov:
Majority Gates vs. General Weighted Threshold Gates. SCT 1992: 2-13 - 1991
- [j12]Johan Håstad, Mikael Goldmann:
On the Power of Small-Depth Threshold Circuits. Comput. Complex. 1: 113-129 (1991) - [j11]William Aiello, Johan Håstad:
Relativized Perfect Zero Knowledge Is Not BPP. Inf. Comput. 93(2): 223-240 (1991) - [j10]William Aiello, Johan Håstad:
Statistical Zero-Knowledge Languages can be Recognized in Two Rounds. J. Comput. Syst. Sci. 42(3): 327-345 (1991) - 1990
- [j9]William Aiello, Shafi Goldwasser, Johan Håstad:
On the power of interaction. Comb. 10(1): 3-25 (1990) - [j8]Johan Håstad:
Tensor Rank is NP-Complete. J. Algorithms 11(4): 644-654 (1990) - [c17]Johan Håstad, Avi Wigderson:
Composition of the Universal Relation. Advances In Computational Complexity Theory 1990: 119-134 - [c16]Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Simple Constructions of Almost k-Wise Independent Random Variables. FOCS 1990: 544-553 - [c15]Johan Håstad, Mikael Goldmann:
On the Power of Small-Depth Threshold Circuits. FOCS 1990: 610-618 - [c14]Johan Håstad:
Pseudo-Random Generators under Uniform Assumptions. STOC 1990: 395-404
1980 – 1989
- 1989
- [j7]Paul Beame, Johan Håstad:
Optimal bounds for decision problems on the CRCW PRAM. J. ACM 36(3): 643-670 (1989) - [j6]Johan Håstad, Bettina Just, J. C. Lagarias, Claus-Peter Schnorr:
Polynomial Time Algorithms for Finding Integer Relations among Real Numbers. SIAM J. Comput. 18(5): 859-881 (1989) - [c13]Johan Håstad:
Tensor Rank is NP-Complete. ICALP 1989: 451-460 - [c12]Johan Håstad, Frank Thomson Leighton, Mark Newman:
Fast Computation Using Faulty Hypercubes (Extended Abstract). STOC 1989: 251-263 - 1988
- [j5]Johan Håstad:
Dual vectors and lower bounds for the nearest lattice point problem. Comb. 8(1): 75-81 (1988) - [j4]Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir:
Reconstructing Truncated Integer Variables Satisfying Linear Congruences. SIAM J. Comput. 17(2): 262-280 (1988) - [j3]Johan Håstad:
Solving Simultaneous Modular Equations of Low Degree. SIAM J. Comput. 17(2): 336-341 (1988) - [c11]Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, Phillip Rogaway:
Everything Provable is Provable in Zero-Knowledge. CRYPTO 1988: 37-56 - 1987
- [j2]Ravi B. Boppana, Johan Håstad, Stathis Zachos:
Does co-NP Have Short Interactive Proofs? Inf. Process. Lett. 25(2): 127-132 (1987) - [j1]Johan Håstad:
One-Way Permutations in NC0. Inf. Process. Lett. 26(3): 153-155 (1987) - [c10]William Aiello, Johan Håstad:
Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds. FOCS 1987: 439-448 - [c9]Paul Beame, Johan Håstad:
Optimal Bounds for Decision Problems on the CRCW PRAM. STOC 1987: 83-93 - [c8]Johan Håstad, Frank Thomson Leighton, Brian Rogoff:
Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract). STOC 1987: 241-253 - [c7]Johan Håstad, Frank Thomson Leighton, Mark Newman:
Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract). STOC 1987: 274-284 - 1986
- [c6]William Aiello, Shafi Goldwasser, Johan Håstad:
On the Power of Interaction. FOCS 1986: 368-379 - [c5]Johan Håstad, Bettina Helfrich, J. C. Lagarias, Claus-Peter Schnorr:
Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. STACS 1986: 105-118 - [c4]Johan Håstad:
Almost Optimal Lower Bounds for Small Depth Circuits. STOC 1986: 6-20 - 1985
- [c3]Johan Håstad:
On Using RSA with Low Exponent in a Public Key Network. CRYPTO 1985: 403-408 - [c2]Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky:
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version). FOCS 1985: 396-407 - [c1]Johan Håstad, Adi Shamir:
The Cryptographic Security of Truncated Linearly Related Variables. STOC 1985: 356-362
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-04-03 00:24 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
