dblp.uni-trier.dewww.uni-trier.de

Johan Håstad Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2009
109EEPer Austrin, Johan Håstad: Randomly supported independence and resistance. STOC 2009: 483-492
2008
108EEJakob Nordström, Johan Håstad: Towards an optimal separation of space and length in resolution. STOC 2008: 701-710
107EEJakob Nordström, Johan Håstad: Towards an Optimal Separation of Space and Length in Resolution CoRR abs/0803.0661: (2008)
106EEJohan Håstad: Every 2-csp Allows Nontrivial Approximation. Computational Complexity 17(4): 549-566 (2008)
105EEJakob Nordström, Johan Håstad: Towards an Optimal Separation of Space and Length in Resolution. Electronic Colloquium on Computational Complexity (ECCC) 15(026): (2008)
104EEJohan Håstad, Mats Näslund: Practical Construction and Analysis of Pseudo-Randomness Primitives. J. Cryptology 21(1): 1-26 (2008)
2007
103EEJohan Håstad: On the Approximation Resistance of a Random Predicate. APPROX-RANDOM 2007: 149-163
102EEJohan Håstad, Svante Linusson, Johan Wästlund: A Smaller Sleeping Bag for a Baby Snake. Discrete & Computational Geometry 38(1): 171 (2007)
101EEJohan Håstad: The Security of the IAPM and IACBC Modes. J. Cryptology 20(2): 153-163 (2007)
100EEJohan Håstad, Avi Wigderson: The Randomized Communication Complexity of Set Disjointness. Theory of Computing 3(1): 211-219 (2007)
2006
99EEJohan Håstad: On Nontrivial Approximation of CSPs. APPROX-RANDOM 2006: 1
98EEJohan Håstad: The square lattice shuffle. Random Struct. Algorithms 29(4): 466-474 (2006)
2005
97EEJohan Håstad: Every 2-CSP allows nontrivial approximation. STOC 2005: 740-746
96EEJohan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. Theory of Computing 1(1): 119-148 (2005)
2004
95EEYevgeniy 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
94EEJohan Håstad, Mats Näslund: The security of all RSA and discrete log bits. J. ACM 51(2): 187-230 (2004)
93EEJohan Håstad, Srinivasan Venkatesh: On the advantage over a random assignment. Random Struct. Algorithms 25(2): 117-149 (2004)
2003
92EEJohan Håstad: Inapproximability Some history and some open problems. IEEE Conference on Computational Complexity 2003: 265-
91EEJohan 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)
90EEJohan Håstad, Avi Wigderson: Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22(2): 139-160 (2003)
2002
89EEJohan 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)
87EEVenkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002)
2001
86EEJohan 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
84EEJohan Håstad, Avi Wigderson: Simple Analysis of Graph Tests for Linearity and PCP. IEEE Conference on Computational Complexity 2001: 244-254
83EEJohan Håstad, Svante Linusson, Johan Wästlund: A Smaller Sleeping Bag for a Baby Snake. Discrete & Computational Geometry 26(1): 173-181 (2001)
82EEJohan 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)
79EEJohan Håstad: A Slight Sharpening of LMN. J. Comput. Syst. Sci. 63(3): 498-508 (2001)
78EEDorit 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
77EEJohan 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
75EEJohan Håstad: Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? ICALP 2000: 235
74EEVenkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of approximate hypergraph coloring Electronic Colloquium on Computational Complexity (ECCC) 7(62): (2000)
73EEJohan Håstad: On bounded occurrence constraint satisfaction. Inf. Process. Lett. 74(1-2): 1-6 (2000)
72EEArne 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
70EEGunnar Andersson, Lars Engebretsen, Johan Håstad: A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p. SODA 1999: 41-50
69EEYonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear Consistency Testing Electronic Colloquium on Computational Complexity (ECCC) 6(25): (1999)
68EEJohan Håstad, Mats Näslund: The Security of all RSA and Discrete Log Bits Electronic Colloquium on Computational Complexity (ECCC) 6(37): (1999)
67EEJohan 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
65EEJohan Håstad, Lars Ivansson, Jens Lagergren: Fitting Points on the Real Line and Its Application to RH Mapping. ESA 1998: 465-476
64EEJohan Håstad, Mats Näslund: The Security of Individual RSA Bits. FOCS 1998: 510-521
63EEJohan Håstad: Some Recent Strong Inapproximability Results. SWAT 1998: 205-209
62EEOded 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)
59EEMikael Goldmann, Johan Håstad: Monotone Circuits for Connectivity Have Depth (log n)2-o(1). SIAM J. Comput. 27(5): 1283-1294 (1998)
1997
58EELiming Cai, Jianer Chen, Johan Håstad: Circuit Bottom Fan-in and Computational Power. IEEE Conference on Computational Complexity 1997: 158-164
57EEJohan Håstad: Some Optimal Inapproximability Results. STOC 1997: 1-10
56EEJohan Håstad: Some optimal inapproximability results Electronic Colloquium on Computational Complexity (ECCC) 4(37): (1997)
55EEJohan 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
53EEJohan Håstad: Testing of the Long Code and Hardness for Clique. STOC 1996: 11-19
52EEOded 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
48EEArne Andersson, Johan Håstad, Ola Petersson: A tight lower bound for searching a sorted array. STOC 1995: 417-426
47EEMikael 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)
45EEJohan 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
44EEArne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson: The complexity of searching a sorted array of strings. STOC 1994: 317-325
43EEJohan 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)
39EEJohan 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
20EEJohan 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
18EEPaul 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
16EEMichael 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
5EEJohan 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
3EEJohan 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

Coauthor Index

1William Aiello [6] [12] [22] [26] [27]
2Noga Alon [25] [29] [33]
3Arne Andersson [44] [48] [72]
4Gunnar Andersson [70] [81]
5Yonatan Aumann [69] [71] [80]
6Per Austrin [109]
7Paul Beame [9] [18]
8Mihir Bellare [49] [51]
9Michael Ben-Or [16]
10Ravi B. Boppana [8]
11Liming Cai [58] [60]
12Richard Chang [40]
13Jianer Chen [58] [60]
14Benny Chor [2] [40]
15Don Coppersmith [49] [51]
16Yevgeniy Dodis [95]
17Dorit Dor [78]
18Lars Engebretsen [70] [81]
19Joel Friedman [2]
20Alan M. Frieze [14]
21Rosario Gennaro [95]
22Mikael Goldmann [24] [28] [30] [31] [32] [41] [47] [59]
23Oded Goldreich [2] [16] [25] [29] [33] [40] [52] [62]
24Shafi Goldwasser [6] [16] [22]
25Per Grape [41]
26Venkatesan Guruswami [74] [76] [87] [88]
27Torben Hagerup [44] [72]
28Juris Hartmanis [40]
29Bettina Helfrich [5]
30Russell Impagliazzo [66]
31Lars Ivansson [65] [91]
32Jakob Jonsson [77]
33Ari Juels [77]
34Stasys Jukna [37] [46]
35Bettina Just [17]
36Ravi Kannan (Ravindran Kannan) [14]
37Subhash Khot [85] [96]
38Joe Kilian [16]
39Marcos A. Kiwi [49] [51]
40Hugo Krawczyk [95]
41Jeffrey C. Lagarias (J. C. Lagarias) [5] [14] [17]
42Jens Lagergren [65] [91]
43Frank Thomson Leighton (Tom Leighton) [10] [11] [19] [50]
44Leonid A. Levin [66]
45Svante Linusson [83] [102]
46Michael Luby [66]
47Silvio Micali [16]
48Mats Näslund [64] [68] [86] [94] [104]
49Mark Newman [10] [19]
50Jakob Nordström [105] [107] [108]
51René Peralta [25] [29] [33]
52Ola Petersson [44] [48] [72]
53Steven Phillips [35] [36]
54Pavel Pudlák [37] [46]
55Michael O. Rabin [69] [71] [80]
56Tal Rabin [95]
57Desh Ranjan [40]
58Alexander A. Razborov [31] [32] [45]
59Phillip Rogaway [16]
60Brian Rogoff [11] [50]
61Pankaj Rohatgi [40]
62Steven Rudich [2]
63Shmuel Safra [35] [36]
64Claus-Peter Schnorr [5] [17]
65A. W. Schrift [34]
66Adi Shamir [1] [14] [34]
67Roman Smolensky [2]
68Madhu Sudan [49] [51] [69] [71] [74] [76] [80] [87] [88]
69Staffan Ulfberg [78]
70Srinivasan Venkatesh [89] [93]
71Johan Wästlund [83] [102]
72Ingo Wegener [42]
73Avi Wigderson [84] [90] [100]
74Norbert Wurm [42]
75Andrew Chi-Chih Yao [45]
76Sang-Zin Yi [42]
77Moti Yung (Mordechai M. Yung) [77]
78Stathis Zachos [8]
79David Zuckerman [88]
80Uri Zwick [78]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)