Johan Håstad
Johan Håstad
Professor i teoretisk datalogi, KTH
Verified email at kth.se
Title
Cited by
Cited by
Year
Some optimal inapproximability results
J Håstad
Journal of the ACM (JACM) 48 (4), 798-859, 2001
20032001
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
1551*1999
Clique is hard to approximate withinn1−ε
J Håstad
Acta Mathematica 182 (1), 105-142, 1999
10811999
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
9701996
Almost optimal lower bounds for small depth circuits
J Hastad
Proceedings of the eighteenth annual ACM symposium on Theory of computing, 6-20, 1986
7871986
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
7171992
Computational limitations for small-depth circuits
JT Håstad
MIT press, 1987
5451987
Tensor rank is NP-complete
J Håstad
Journal of algorithms (Print) 11 (4), 644-654, 1990
5151990
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
4731985
Does co-NP have short interactive proofs?
RB Boppana, J Hastad, S Zachos
Information Processing Letters 25 (2), 127-132, 1987
4711987
On the power of small-depth threshold circuits
J Håstad, M Goldmann
Computational Complexity 1 (2), 113-129, 1991
3071991
Solving simultaneous modular equations of low degree
J Hastad
siam Journal on Computing 17 (2), 336-341, 1988
3001988
Optimal bounds for decision problems on the CRCW PRAM
P Beame, J Hastad
Journal of the ACM (JACM) 36 (3), 643-670, 1989
2931989
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
2901988
Analysis of backoff protocols for multiple access channels
J Håstad, T Leighton, B Rogoff
SIAM journal on computing 25 (4), 740-774, 1996
2681996
Majority gates vs. general weighted threshold gates
M Goldmann, J Håstad, A Razborov
Computational Complexity 2 (4), 277-300, 1992
2371992
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
2191996
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
1891985
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
1882004
Pseudo-random generators under uniform assumptions
J Håstad
Proceedings of the twenty-second annual ACM symposium on Theory of computing …, 1990
1711990
The system can't perform the operation now. Try again later.
Articles 1–20