Johan Håstad
Johan Håstad
Professor i teoretisk datalogi, KTH
Verified email at kth.se
TitleCited byYear
Some optimal inapproximability results
J Håstad
Journal of the ACM (JACM) 48 (4), 798-859, 2001
19062001
Clique is hard to approximate within n/sup 1-/spl epsiv
J Hastad
Proceedings of 37th Conference on Foundations of Computer Science, 627-636, 1996
15861996
A pseudorandom generator from any one-way function
J Håstad, R Impagliazzo, LA Levin, M Luby
SIAM Journal on Computing 28 (4), 1364-1396, 1999
1457*1999
Almost optimal lower bounds for small depth circuits
J Hastad
Proceedings of the eighteenth annual ACM symposium on Theory of computing, 6-20, 1986
7421986
Simple constructions of almost k‐wise independent random variables
N Alon, O Goldreich, J Håstad, R Peralta
Random Structures & Algorithms 3 (3), 289-304, 1992
6871992
Computational limitations of small-depth circuits
J Håstad
5131987
Does co-NP have short interactive proofs?
RB Boppana, J Hastad, S Zachos
Information Processing Letters 25 (2), 127-132, 1987
4601987
The bit extraction problem or t-resilient functions
B Chor, O Goldreich, J Hasted, J Freidmann, S Rudich, R Smolensky
26th Annual Symposium on Foundations of Computer Science (sfcs 1985), 396-407, 1985
4591985
Tensor rank is NP-complete
J Håstad
Journal of Algorithms 11 (4), 644-654, 1990
4401990
Solving simultaneous modular equations of low degree
J Hastad
siam Journal on Computing 17 (2), 336-341, 1988
3151988
Optimal bounds for decision problems on the CRCW PRAM
P Beame, J Hastad
Journal of the ACM (JACM) 36 (3), 643-670, 1989
2871989
On the power of small-depth threshold circuits
J Håstad, M Goldmann
Computational Complexity 1 (2), 113-129, 1991
2841991
Everything provable is provable in zero-knowledge
M Ben-Or, O Goldreich, S Goldwasser, J Håstad, J Kilian, S Micali, ...
Conference on the Theory and Application of Cryptography, 37-56, 1988
2681988
Analysis of backoff protocols for multiple access channels
J Håstad, T Leighton, B Rogoff
SIAM journal on computing 25 (4), 740-774, 1996
2621996
Majority gates vs. general weighted threshold gates
M Goldmann, J Håstad, A Razborov
Computational Complexity 2 (4), 277-300, 1992
2271992
Linearity testing in characteristic two
M Bellare, D Coppersmith, J Hastad, M Kiwi, M Sudan
IEEE Transactions on Information Theory 42 (6), 1781-1795, 1996
2181996
N using RSA with low exponent in a public key network
J Hastad
Conference on the Theory and Application of Cryptographic Techniques, 403-408, 1985
1801985
Randomness extraction and key derivation using the CBC, cascade and HMAC modes
Y Dodis, R Gennaro, J Håstad, H Krawczyk, T Rabin
Annual International Cryptology Conference, 494-510, 2004
1792004
Pseudo-random generators under uniform assumptions
J Håstad
Proceedings of the twenty-second annual ACM symposium on Theory of computing …, 1990
1691990
Reconstructing truncated integer variables satisfying linear congruences
AM Frieze, J Hastad, R Kannan, JC Lagarias, A Shamir
SIAM Journal on Computing 17 (2), 262-280, 1988
1571988
The system can't perform the operation now. Try again later.
Articles 1–20