 | 2009 |
|---|
| 109 |       | Per Austrin,
Johan Håstad:
Randomly supported independence and resistance.
STOC 2009: 483-492 |
| 2008 |
|---|
| 108 | | Jakob Nordström,
Johan Håstad:
Towards an optimal separation of space and length in resolution.
STOC 2008: 701-710 |
| 107 | | Jakob Nordström,
Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution
CoRR abs/0803.0661: (2008) |
| 106 | | Johan Håstad:
Every 2-csp Allows Nontrivial Approximation.
Computational Complexity 17(4): 549-566 (2008) |
| 105 | | Jakob Nordström,
Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution.
Electronic Colloquium on Computational Complexity (ECCC) 15(026): (2008) |
| 104 | | Johan Håstad,
Mats Näslund:
Practical Construction and Analysis of Pseudo-Randomness Primitives.
J. Cryptology 21(1): 1-26 (2008) |
| 2007 |
|---|
| 103 | | Johan Håstad:
On the Approximation Resistance of a Random Predicate.
APPROX-RANDOM 2007: 149-163 |
| 102 | | Johan Håstad,
Svante Linusson,
Johan Wästlund:
A Smaller Sleeping Bag for a Baby Snake.
Discrete & Computational Geometry 38(1): 171 (2007) |
| 101 | | Johan Håstad:
The Security of the IAPM and IACBC Modes.
J. Cryptology 20(2): 153-163 (2007) |
| 100 | | Johan Håstad,
Avi Wigderson:
The Randomized Communication Complexity of Set Disjointness.
Theory of Computing 3(1): 211-219 (2007) |
| 2006 |
|---|
| 99 | | Johan Håstad:
On Nontrivial Approximation of CSPs.
APPROX-RANDOM 2006: 1 |
| 98 | | Johan Håstad:
The square lattice shuffle.
Random Struct. Algorithms 29(4): 466-474 (2006) |
| 2005 |
|---|
| 97 | | Johan Håstad:
Every 2-CSP allows nontrivial approximation.
STOC 2005: 740-746 |
| 96 | | Johan Håstad,
Subhash Khot:
Query Efficient PCPs with Perfect Completeness.
Theory of Computing 1(1): 119-148 (2005) |
| 2004 |
|---|
| 95 | | 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 |
| 94 | | Johan Håstad,
Mats Näslund:
The security of all RSA and discrete log bits.
J. ACM 51(2): 187-230 (2004) |
| 93 | | Johan Håstad,
Srinivasan Venkatesh:
On the advantage over a random assignment.
Random Struct. Algorithms 25(2): 117-149 (2004) |
| 2003 |
|---|
| 92 | | Johan Håstad:
Inapproximability Some history and some open problems.
IEEE Conference on Computational Complexity 2003: 265- |
| 91 | | 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) |
| 90 | | Johan Håstad,
Avi Wigderson:
Simple analysis of graph tests for linearity and PCP.
Random Struct. Algorithms 22(2): 139-160 (2003) |
| 2002 |
|---|
| 89 | | Johan Håstad,
Srinivasan Venkatesh:
On the advantage over a random assignment.
STOC 2002: 43-52 |
| 88 |  | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan,
David Zuckerman:
Combinatorial bounds for list decoding.
IEEE Transactions on Information Theory 48(5): 1021-1034 (2002) |
| 87 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput. 31(6): 1663-1686 (2002) |
| 2001 |
|---|
| 86 | | Johan Håstad,
Mats Näslund:
Practical Construction and Analysis of Pseudo-Randomness Primitives.
ASIACRYPT 2001: 442-459 |
| 85 | | Johan Håstad,
Subhash Khot:
Query Efficient PCPs with Perfect Completeness.
FOCS 2001: 610-619 |
| 84 | | Johan Håstad,
Avi Wigderson:
Simple Analysis of Graph Tests for Linearity and PCP.
IEEE Conference on Computational Complexity 2001: 244-254 |
| 83 | | Johan Håstad,
Svante Linusson,
Johan Wästlund:
A Smaller Sleeping Bag for a Baby Snake.
Discrete & Computational Geometry 26(1): 173-181 (2001) |
| 82 | | Johan Håstad:
Some optimal inapproximability results.
J. ACM 48(4): 798-859 (2001) |
| 81 | | 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) |
| 80 | | Yonatan Aumann,
Johan Håstad,
Michael O. Rabin,
Madhu Sudan:
Linear-Consistency Testing.
J. Comput. Syst. Sci. 62(4): 589-607 (2001) |
| 79 | | Johan Håstad:
A Slight Sharpening of LMN.
J. Comput. Syst. Sci. 63(3): 498-508 (2001) |
| 78 | | Dorit Dor,
Johan Håstad,
Staffan Ulfberg,
Uri Zwick:
On Lower Bounds for Selecting the Median.
SIAM J. Discrete Math. 14(3): 299-311 (2001) |
| 2000 |
|---|
| 77 | | Johan Håstad,
Jakob Jonsson,
Ari Juels,
Moti Yung:
Funkspiel schemes: an alternative to conventional tamper resistance.
ACM Conference on Computer and Communications Security 2000: 125-133 |
| 76 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of Approximate Hypergraph Coloring.
FOCS 2000: 149-158 |
| 75 | | Johan Håstad:
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?
ICALP 2000: 235 |
| 74 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC) 7(62): (2000) |
| 73 | | Johan Håstad:
On bounded occurrence constraint satisfaction.
Inf. Process. Lett. 74(1-2): 1-6 (2000) |
| 72 | | 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) |
| 1999 |
|---|
| 71 | | Yonatan Aumann,
Johan Håstad,
Michael O. Rabin,
Madhu Sudan:
Linear Consistency Testing.
RANDOM-APPROX 1999: 109-120 |
| 70 | | 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 |
| 69 | | Yonatan Aumann,
Johan Håstad,
Michael O. Rabin,
Madhu Sudan:
Linear Consistency Testing
Electronic Colloquium on Computational Complexity (ECCC) 6(25): (1999) |
| 68 | | Johan Håstad,
Mats Näslund:
The Security of all RSA and Discrete Log Bits
Electronic Colloquium on Computational Complexity (ECCC) 6(37): (1999) |
| 67 | | Johan Håstad:
On approximating CSP-B
Electronic Colloquium on Computational Complexity (ECCC) 6(39): (1999) |
| 66 | | 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) |
| 1998 |
|---|
| 65 | | Johan Håstad,
Lars Ivansson,
Jens Lagergren:
Fitting Points on the Real Line and Its Application to RH Mapping.
ESA 1998: 465-476 |
| 64 | | Johan Håstad,
Mats Näslund:
The Security of Individual RSA Bits.
FOCS 1998: 510-521 |
| 63 | | Johan Håstad:
Some Recent Strong Inapproximability Results.
SWAT 1998: 205-209 |
| 62 | | Oded Goldreich,
Johan Håstad:
On the Complexity of Interactive Proofs with Bounded Communication.
Inf. Process. Lett. 67(4): 205-214 (1998) |
| 61 | | Johan Håstad:
The Shrinkage Exponent of de Morgan Formulas is 2.
SIAM J. Comput. 27(1): 48-64 (1998) |
| 60 | | Liming Cai,
Jianer Chen,
Johan Håstad:
Circuit Bottom Fan-In and Computational Power.
SIAM J. Comput. 27(2): 341-355 (1998) |
| 59 | | Mikael Goldmann,
Johan Håstad:
Monotone Circuits for Connectivity Have Depth (log n)2-o(1).
SIAM J. Comput. 27(5): 1283-1294 (1998) |
| 1997 |
|---|
| 58 | | Liming Cai,
Jianer Chen,
Johan Håstad:
Circuit Bottom Fan-in and Computational Power.
IEEE Conference on Computational Complexity 1997: 158-164 |
| 57 | | Johan Håstad:
Some Optimal Inapproximability Results.
STOC 1997: 1-10 |
| 56 | | Johan Håstad:
Some optimal inapproximability results
Electronic Colloquium on Computational Complexity (ECCC) 4(37): (1997) |
| 55 | | Johan Håstad:
Clique is hard to approximate within n1-epsilon
Electronic Colloquium on Computational Complexity (ECCC) 4(38): (1997) |
| 1996 |
|---|
| 54 | | Johan Håstad:
Clique is Hard to Approximate Within n1-epsilon.
FOCS 1996: 627-636 |
| 53 | | Johan Håstad:
Testing of the Long Code and Hardness for Clique.
STOC 1996: 11-19 |
| 52 | | Oded Goldreich,
Johan Håstad:
On the Message Complexity of Interactive Proof Systems
Electronic Colloquium on Computational Complexity (ECCC) 3(18): (1996) |
| 51 | | Mihir Bellare,
Don Coppersmith,
Johan Håstad,
Marcos A. Kiwi,
Madhu Sudan:
Linearity testing in characteristic two.
IEEE Transactions on Information Theory 42(6): 1781-1795 (1996) |
| 50 | | Johan Håstad,
Frank Thomson Leighton,
Brian Rogoff:
Analysis of Backoff Protocols for Multiple Access Channels.
SIAM J. Comput. 25(4): 740-774 (1996) |
| 1995 |
|---|
| 49 | | Mihir Bellare,
Don Coppersmith,
Johan Håstad,
Marcos A. Kiwi,
Madhu Sudan:
Linearity Testing in Characteristic Two.
FOCS 1995: 432-441 |
| 48 | | Arne Andersson,
Johan Håstad,
Ola Petersson:
A tight lower bound for searching a sorted array.
STOC 1995: 417-426 |
| 47 | | Mikael Goldmann,
Johan Håstad:
Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract).
STOC 1995: 569-574 |
| 46 | | Johan Håstad,
Stasys Jukna,
Pavel Pudlák:
Top-Down Lower Bounds for Depth-Three Circuits.
Computational Complexity 5(2): 99-112 (1995) |
| 45 | | 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) |
| 1994 |
|---|
| 44 | | Arne Andersson,
Torben Hagerup,
Johan Håstad,
Ola Petersson:
The complexity of searching a sorted array of strings.
STOC 1994: 317-325 |
| 43 | | Johan Håstad:
Recent Results in Hardness of Approximation.
SWAT 1994: 231-239 |
| 42 | | 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) |
| 41 | | Mikael Goldmann,
Per Grape,
Johan Håstad:
On Average Time Hierarchies.
Inf. Process. Lett. 49(1): 15-20 (1994) |
| 40 | | 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) |
| 39 | | Johan Håstad:
On the Size of Weights for Threshold Gates.
SIAM J. Discrete Math. 7(3): 484-492 (1994) |
| 1993 |
|---|
| 38 | | Johan Håstad:
The shrinkage exponent is 2
FOCS 1993: 114-123 |
| 37 | | Johan Håstad,
Stasys Jukna,
Pavel Pudlák:
Top-Down Lower Bounds for Depth 3 Circuits
FOCS 1993: 124-129 |
| 36 | | Johan Håstad,
Steven Phillips,
Shmuel Safra:
A Well-Characterized Approximation Problem.
ISTCS 1993: 261-265 |
| 35 | | Johan Håstad,
Steven Phillips,
Shmuel Safra:
A Well-Characterized Approximation Problem.
Inf. Process. Lett. 47(6): 301-305 (1993) |
| 34 | | 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) |
| 33 | | 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) |
| 1992 |
|---|
| 32 | | Mikael Goldmann,
Johan Håstad,
Alexander A. Razborov:
Majority Gates vs. General Weighted Threshold Gates.
Structure in Complexity Theory Conference 1992: 2-13 |
| 31 | | Mikael Goldmann,
Johan Håstad,
Alexander A. Razborov:
Majority Gates VS. General Weighted Threshold Gates.
Computational Complexity 2: 277-300 (1992) |
| 30 | | Mikael Goldmann,
Johan Håstad:
A Simple Lower Bound for Monotone Clique Using a Communication Game.
Inf. Process. Lett. 41(4): 221-226 (1992) |
| 29 | | 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) |
| 1991 |
|---|
| 28 | | Johan Håstad,
Mikael Goldmann:
On the Power of Small-Depth Threshold Circuits.
Computational Complexity 1: 113-129 (1991) |
| 27 | | William Aiello,
Johan Håstad:
Relativized Perfect Zero Knowledge Is Not BPP
Inf. Comput. 93(2): 223-240 (1991) |
| 26 | | 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 |
|---|
| 25 | | Noga Alon,
Oded Goldreich,
Johan Håstad,
René Peralta:
Simple Constructions of Almost k-Wise Independent Random Variables
FOCS 1990: 544-553 |
| 24 | | Johan Håstad,
Mikael Goldmann:
On the Power of Small-Depth Threshold Circuits
FOCS 1990: 610-618 |
| 23 | | Johan Håstad:
Pseudo-Random Generators under Uniform Assumptions
STOC 1990: 395-404 |
| 22 | | William Aiello,
Shafi Goldwasser,
Johan Håstad:
On the power of interaction.
Combinatorica 10(1): 3-25 (1990) |
| 21 | | Johan Håstad:
Tensor Rank is NP-Complete.
J. Algorithms 11(4): 644-654 (1990) |
| 1989 |
|---|
| 20 | | Johan Håstad:
Tensor Rank is NP-Complete.
ICALP 1989: 451-460 |
| 19 | | Johan Håstad,
Frank Thomson Leighton,
Mark Newman:
Fast Computation Using Faulty Hypercubes (Extended Abstract)
STOC 1989: 251-263 |
| 18 | | Paul Beame,
Johan Håstad:
Optimal bounds for decision problems on the CRCW PRAM.
J. ACM 36(3): 643-670 (1989) |
| 17 | | 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) |
| 1988 |
|---|
| 16 | | 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 |
| 15 | | Johan Håstad:
Dual vectors and lower bounds for the nearest lattice point problem.
Combinatorica 8(1): 75-81 (1988) |
| 14 | | 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) |
| 13 | | Johan Håstad:
Solving Simultaneous Modular Equations of Low Degree.
SIAM J. Comput. 17(2): 336-341 (1988) |
| 1987 |
|---|
| 12 | | William Aiello,
Johan Håstad:
Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds
FOCS 1987: 439-448 |
| 11 | | Johan Håstad,
Frank Thomson Leighton,
Brian Rogoff:
Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract)
STOC 1987: 241-253 |
| 10 | | Johan Håstad,
Frank Thomson Leighton,
Mark Newman:
Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)
STOC 1987: 274-284 |
| 9 | | Paul Beame,
Johan Håstad:
Optimal Bounds for Decision Problems on the CRCW PRAM
STOC 1987: 83-93 |
| 8 | | Ravi B. Boppana,
Johan Håstad,
Stathis Zachos:
Does co-NP Have Short Interactive Proofs?
Inf. Process. Lett. 25(2): 127-132 (1987) |
| 7 | | Johan Håstad:
One-Way Permutations in NC0.
Inf. Process. Lett. 26(3): 153-155 (1987) |
| 1986 |
|---|
| 6 | | William Aiello,
Shafi Goldwasser,
Johan Håstad:
On the Power of Interaction
FOCS 1986: 368-379 |
| 5 | | 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 |
| 4 | | Johan Håstad:
Almost Optimal Lower Bounds for Small Depth Circuits
STOC 1986: 6-20 |
| 1985 |
|---|
| 3 | | Johan Håstad:
On Using RSA with Low Exponent in a Public Key Network.
CRYPTO 1985: 403-408 |
| 2 | | 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 |
| 1 | | Johan Håstad,
Adi Shamir:
The Cryptographic Security of Truncated Linearly Related Variables
STOC 1985: 356-362 |
