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

Johan Håstad Coauthor index pubzone.org

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

DBLP keys2012
126Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPer Austrin, Johan Håstad: On the Usefulness of Predicates CoRR abs/1204.5662: (2012)
125Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates. TOCT 4(1): 2 (2012)
2011
124Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Satisfying Degree-d Equations over GF[2] n. APPROX-RANDOM 2011: 242-253
123Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLBoaz 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)
122Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLBoaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer: Making the long code shorter, with applications to the Unique Games Conjecture. Electronic Colloquium on Computational Complexity (ECCC) 18: 142 (2011)
121Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar: Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electronic Colloquium on Computational Complexity (ECCC) 18: 27 (2011)
120Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. IEEE Transactions on Information Theory 57(2): 718-725 (2011)
119Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPer Austrin, Johan Håstad: Randomly Supported Independence and Resistance. SIAM J. Comput. 40(1): 1-27 (2011)
118Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan 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)
2010
117Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates. APPROX-RANDOM 2010: 110-123
116Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the list-decodability of random linear codes. STOC 2010: 409-416
115Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Rafael Pass, Douglas Wikström, Krzysztof Pietrzak: An Efficient Parallel Repetition Theorem. TCC 2010: 1-18
114Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes CoRR abs/1001.1386: (2010)
113Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. Computational Complexity 19(2): 151-152 (2010)
112Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates. Electronic Colloquium on Computational Complexity (ECCC) 17: 132 (2010)
111Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 3 (2010)
2009
110Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPer Austrin, Johan Håstad: Randomly supported independence and resistance. STOC 2009: 483-492
109Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On the Approximation Resistance of a Random Predicate. Computational Complexity 18(3): 413-434 (2009)
2008
108Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJakob Nordström, Johan Håstad: Towards an optimal separation of space and length in resolution. STOC 2008: 701-710
107Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJakob Nordström, Johan Håstad: Towards an Optimal Separation of Space and Length in Resolution CoRR abs/0803.0661: (2008)
106Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Every 2-csp Allows Nontrivial Approximation. Computational Complexity 17(4): 549-566 (2008)
105Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJakob Nordström, Johan Håstad: Towards an Optimal Separation of Space and Length in Resolution. Electronic Colloquium on Computational Complexity (ECCC) 15(026): (2008)
104Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mats Näslund: Practical Construction and Analysis of Pseudo-Randomness Primitives. J. Cryptology 21(1): 1-26 (2008)
2007
103Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On the Approximation Resistance of a Random Predicate. APPROX-RANDOM 2007: 149-163
102Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Svante Linusson, Johan Wästlund: A Smaller Sleeping Bag for a Baby Snake. Discrete & Computational Geometry 38(1): 171 (2007)
101Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: The Security of the IAPM and IACBC Modes. J. Cryptology 20(2): 153-163 (2007)
100Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Avi Wigderson: The Randomized Communication Complexity of Set Disjointness. Theory of Computing 3(1): 211-219 (2007)
2006
99Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On Nontrivial Approximation of CSPs. APPROX-RANDOM 2006: 1
98Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: The square lattice shuffle. Random Struct. Algorithms 29(4): 466-474 (2006)
2005
97Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Every 2-CSP allows nontrivial approximation. STOC 2005: 740-746
96Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. Theory of Computing 1(1): 119-148 (2005)
2004
95Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLYevgeniy 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
94Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mats Näslund: The security of all RSA and discrete log bits. J. ACM 51(2): 187-230 (2004)
93Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Srinivasan Venkatesh: On the advantage over a random assignment. Random Struct. Algorithms 25(2): 117-149 (2004)
2003
92Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Inapproximability Some history and some open problems. IEEE Conference on Computational Complexity 2003: 265-
91Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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)
90Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Avi Wigderson: Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22(2): 139-160 (2003)
2002
89Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Srinivasan Venkatesh: On the advantage over a random assignment. STOC 2002: 43-52
88Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman: Combinatorial bounds for list decoding. IEEE Transactions on Information Theory 48(5): 1021-1034 (2002)
87Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002)
2001
86Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mats Näslund: Practical Construction and Analysis of Pseudo-Randomness Primitives. ASIACRYPT 2001: 442-459
85Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. FOCS 2001: 610-619
84Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Avi Wigderson: Simple Analysis of Graph Tests for Linearity and PCP. IEEE Conference on Computational Complexity 2001: 244-254
83Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Svante Linusson, Johan Wästlund: A Smaller Sleeping Bag for a Baby Snake. Discrete & Computational Geometry 26(1): 173-181 (2001)
82Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Some optimal inapproximability results. J. ACM 48(4): 798-859 (2001)
81Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGunnar 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)
80Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLYonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear-Consistency Testing. J. Comput. Syst. Sci. 62(4): 589-607 (2001)
79Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: A Slight Sharpening of LMN. J. Comput. Syst. Sci. 63(3): 498-508 (2001)
78Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDorit 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
77Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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
76Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158
75Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? ICALP 2000: 235
74Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLVenkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of approximate hypergraph coloring Electronic Colloquium on Computational Complexity (ECCC) 7(62): (2000)
73Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On bounded occurrence constraint satisfaction. Inf. Process. Lett. 74(1-2): 1-6 (2000)
72Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLArne 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
71no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLYonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear Consistency Testing. RANDOM-APPROX 1999: 109-120
70Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGunnar Andersson, Lars Engebretsen, Johan Håstad: A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p. SODA 1999: 41-50
69Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLYonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear Consistency Testing Electronic Colloquium on Computational Complexity (ECCC) 6(25): (1999)
68Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mats Näslund: The Security of all RSA and Discrete Log Bits Electronic Colloquium on Computational Complexity (ECCC) 6(37): (1999)
67Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On approximating CSP-B Electronic Colloquium on Computational Complexity (ECCC) 6(39): (1999)
66Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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
65Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Lars Ivansson, Jens Lagergren: Fitting Points on the Real Line and Its Application to RH Mapping. ESA 1998: 465-476
64Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mats Näslund: The Security of Individual RSA Bits. FOCS 1998: 510-521
63Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Some Recent Strong Inapproximability Results. SWAT 1998: 205-209
62Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLOded Goldreich, Johan Håstad: On the Complexity of Interactive Proofs with Bounded Communication. Inf. Process. Lett. 67(4): 205-214 (1998)
61Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput. 27(1): 48-64 (1998)
60Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLiming Cai, Jianer Chen, Johan Håstad: Circuit Bottom Fan-In and Computational Power. SIAM J. Comput. 27(2): 341-355 (1998)
59Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Johan Håstad: Monotone Circuits for Connectivity Have Depth (log n)2-o(1). SIAM J. Comput. 27(5): 1283-1294 (1998)
1997
58Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLiming Cai, Jianer Chen, Johan Håstad: Circuit Bottom Fan-in and Computational Power. IEEE Conference on Computational Complexity 1997: 158-164
57Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Some Optimal Inapproximability Results. STOC 1997: 1-10
56Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Some optimal inapproximability results Electronic Colloquium on Computational Complexity (ECCC) 4(37): (1997)
55Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Clique is hard to approximate within n1-epsilon Electronic Colloquium on Computational Complexity (ECCC) 4(38): (1997)
1996
54Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Clique is Hard to Approximate Within n1-epsilon. FOCS 1996: 627-636
53Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Testing of the Long Code and Hardness for Clique. STOC 1996: 11-19
52Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLOded Goldreich, Johan Håstad: On the Message Complexity of Interactive Proof Systems Electronic Colloquium on Computational Complexity (ECCC) 3(18): (1996)
51Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMihir 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)
50Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Frank Thomson Leighton, Brian Rogoff: Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput. 25(4): 740-774 (1996)
1995
49Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan: Linearity Testing in Characteristic Two. FOCS 1995: 432-441
48Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLArne Andersson, Johan Håstad, Ola Petersson: A tight lower bound for searching a sorted array. STOC 1995: 417-426
47Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Johan Håstad: Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract). STOC 1995: 569-574
46Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Stasys Jukna, Pavel Pudlák: Top-Down Lower Bounds for Depth-Three Circuits. Computational Complexity 5(2): 99-112 (1995)
45Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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
44Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLArne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson: The complexity of searching a sorted array of strings. STOC 1994: 317-325
43Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Recent Results in Hardness of Approximation. SWAT 1994: 231-239
42Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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)
41Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Per Grape, Johan Håstad: On Average Time Hierarchies. Inf. Process. Lett. 49(1): 15-20 (1994)
40Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRichard 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)
39Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On the Size of Weights for Threshold Gates. SIAM J. Discrete Math. 7(3): 484-492 (1994)
1993
38Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: The shrinkage exponent is 2 FOCS 1993: 114-123
37Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Stasys Jukna, Pavel Pudlák: Top-Down Lower Bounds for Depth 3 Circuits FOCS 1993: 124-129
36no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Steven Phillips, Shmuel Safra: A Well-Characterized Approximation Problem. ISTCS 1993: 261-265
35Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Steven Phillips, Shmuel Safra: A Well-Characterized Approximation Problem. Inf. Process. Lett. 47(6): 301-305 (1993)
34Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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)
33Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNoga 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
32no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Johan Håstad, Alexander A. Razborov: Majority Gates vs. General Weighted Threshold Gates. Structure in Complexity Theory Conference 1992: 2-13
31Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Johan Håstad, Alexander A. Razborov: Majority Gates VS. General Weighted Threshold Gates. Computational Complexity 2: 277-300 (1992)
30Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Johan Håstad: A Simple Lower Bound for Monotone Clique Using a Communication Game. Inf. Process. Lett. 41(4): 221-226 (1992)
29Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNoga 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
28Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mikael Goldmann: On the Power of Small-Depth Threshold Circuits. Computational Complexity 1: 113-129 (1991)
27Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWilliam Aiello, Johan Håstad: Relativized Perfect Zero Knowledge Is Not BPP Inf. Comput. 93(2): 223-240 (1991)
26Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWilliam Aiello, Johan Håstad: Statistical Zero-Knowledge Languages can be Recognized in Two Rounds. J. Comput. Syst. Sci. 42(3): 327-345 (1991)
1990
25Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNoga Alon, Oded Goldreich, Johan Håstad, René Peralta: Simple Constructions of Almost k-Wise Independent Random Variables FOCS 1990: 544-553
24Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Mikael Goldmann: On the Power of Small-Depth Threshold Circuits FOCS 1990: 610-618
23Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Pseudo-Random Generators under Uniform Assumptions STOC 1990: 395-404
22Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWilliam Aiello, Shafi Goldwasser, Johan Håstad: On the power of interaction. Combinatorica 10(1): 3-25 (1990)
21Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Tensor Rank is NP-Complete. J. Algorithms 11(4): 644-654 (1990)
1989
20Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Tensor Rank is NP-Complete. ICALP 1989: 451-460
19Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Frank Thomson Leighton, Mark Newman: Fast Computation Using Faulty Hypercubes (Extended Abstract) STOC 1989: 251-263
18Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPaul Beame, Johan Håstad: Optimal bounds for decision problems on the CRCW PRAM. J. ACM 36(3): 643-670 (1989)
17Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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
16Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMichael 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
15Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Dual vectors and lower bounds for the nearest lattice point problem. Combinatorica 8(1): 75-81 (1988)
14Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAlan 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)
13Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Solving Simultaneous Modular Equations of Low Degree. SIAM J. Comput. 17(2): 336-341 (1988)
1987
12Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWilliam Aiello, Johan Håstad: Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds FOCS 1987: 439-448
11Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Frank Thomson Leighton, Brian Rogoff: Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract) STOC 1987: 241-253
10Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Frank Thomson Leighton, Mark Newman: Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract) STOC 1987: 274-284
9Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPaul Beame, Johan Håstad: Optimal Bounds for Decision Problems on the CRCW PRAM STOC 1987: 83-93
8Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRavi B. Boppana, Johan Håstad, Stathis Zachos: Does co-NP Have Short Interactive Proofs? Inf. Process. Lett. 25(2): 127-132 (1987)
7Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: One-Way Permutations in NC0. Inf. Process. Lett. 26(3): 153-155 (1987)
1986
6Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWilliam Aiello, Shafi Goldwasser, Johan Håstad: On the Power of Interaction FOCS 1986: 368-379
5Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad, Bettina Helfrich, J. C. Lagarias, Claus-Peter Schnorr: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. STACS 1986: 105-118
4Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: Almost Optimal Lower Bounds for Small Depth Circuits STOC 1986: 6-20
1985
3Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan Håstad: On Using RSA with Low Exponent in a Public Key Network. CRYPTO 1985: 403-408
2Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLBenny 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
1Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJohan 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 [110] [119] [126]
7Boaz Barak [122] [123]
8Paul Beame [9] [18]
9Mihir Bellare [49] [51]
10Michael Ben-Or [16]
11Ravi B. Boppana [8]
12Liming Cai [58] [60]
13Richard Chang [40]
14Moses Charikar [118] [121]
15Jianer Chen [58] [60]
16Mahdi Cheraghchi [112] [117] [125]
17Benny Chor [2] [40]
18Don Coppersmith [49] [51]
19Yevgeniy Dodis [95]
20Dorit Dor [78]
21Lars Engebretsen [70] [81]
22Joel Friedman [2]
23Alan M. Frieze [14]
24Rosario Gennaro [95]
25Mikael Goldmann [24] [28] [30] [31] [32] [41] [47] [59]
26Oded Goldreich [2] [16] [25] [29] [33] [40] [52] [62]
27Shafi Goldwasser [6] [16] [22]
28Parikshit Gopalan [122] [123]
29Per Grape [41]
30Venkatesan Guruswami [74] [76] [87] [88] [111] [114] [116] [118] [120] [121]
31Torben Hagerup [44] [72]
32Juris Hartmanis [40]
33Bettina Helfrich [5]
34Russell Impagliazzo [66]
35Marcus Isaksson [112] [117] [125]
36Lars Ivansson [65] [91]
37Jakob Jonsson [77]
38Ari Juels [77]
39Stasys Jukna [37] [46]
40Bettina Just [17]
41Ravi Kannan (Ravindran Kannan) [14]
42Subhash Khot [85] [96]
43Joe Kilian [16]
44Marcos A. Kiwi [49] [51]
45Swastik Kopparty [111] [114] [116] [120]
46Hugo Krawczyk [95]
47Jeffrey C. Lagarias (J. C. Lagarias) [5] [14] [17]
48Jens Lagergren [65] [91]
49Frank Thomson Leighton (Tom Leighton) [10] [11] [19] [50]
50Leonid A. Levin [66]
51Svante Linusson [83] [102]
52Michael Luby [66]
53Rajsekar Manokaran [118] [121]
54Raghu Meka [122] [123]
55Silvio Micali [16]
56Mats Näslund [64] [68] [86] [94] [104]
57Mark Newman [10] [19]
58Jakob Nordström [105] [107] [108]
59Rafael Pass [115]
60René Peralta [25] [29] [33]
61Ola Petersson [44] [48] [72]
62Steven Phillips [35] [36]
63Krzysztof Pietrzak [115]
64Pavel Pudlák [37] [46]
65Michael O. Rabin [69] [71] [80]
66Tal Rabin [95]
67Prasad Raghavendra [118] [121] [122] [123]
68Desh Ranjan [40]
69Alexander A. Razborov [31] [32] [45]
70Phillip Rogaway [16]
71Brian Rogoff [11] [50]
72Pankaj Rohatgi [40]
73Steven Rudich [2]
74Shmuel Safra (Muli Safra) [35] [36]
75Claus-Peter Schnorr [5] [17]
76A. W. Schrift [34]
77Adi Shamir [1] [14] [34]
78Roman Smolensky [2]
79David Steurer [122] [123]
80Madhu Sudan [49] [51] [69] [71] [74] [76] [80] [87] [88]
81Ola Svensson [112] [117] [125]
82Staffan Ulfberg [78]
83Srinivasan Venkatesh [89] [93]
84Johan Wästlund [83] [102]
85Ingo Wegener [42]
86Avi Wigderson [84] [90] [100]
87Douglas Wikström [115]
88Norbert Wurm [42]
89Andrew Chi-Chih Yao (Andrew C. Yao) [45]
90Sang-Zin Yi [42]
91Moti Yung (Mordechai M. Yung) [77]
92Stathis Zachos [8]
93David Zuckerman [88]
94Uri Zwick [78]

Colors in the list of coauthors

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Free | Complete | Author
Last update Thu May 31 18:55:10 2012 CET by the DBLP Team — This material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page