| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson |
Approximating Linear Threshold Predicates.  |
TOCT  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Johan Håstad |
On the Usefulness of Predicates |
CoRR |
2012 |
DBLP BibTeX RDF |
|
| 1 | Boaz 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) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan 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) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Boaz 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 |
2011 |
DBLP BibTeX RDF |
|
| 1 | Per Austrin, Johan Håstad |
Randomly Supported Independence and Resistance. |
SIAM J. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan 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. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Swastik Kopparty |
On the List-Decodability of Random Linear Codes. |
IEEE Transactions on Information Theory |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Satisfying Degree-d Equations over GF[2] n. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson |
Approximating Linear Threshold Predicates. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Swastik Kopparty |
On the List-Decodability of Random Linear Codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad |
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Swastik Kopparty |
On the List-Decodability of Random Linear Codes |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad, Rafael Pass, Douglas Wikström, Krzysztof Pietrzak |
An Efficient Parallel Repetition Theorem. |
TCC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson |
Approximating Linear Threshold Predicates. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Swastik Kopparty |
On the list-decodability of random linear codes. |
STOC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On the Approximation Resistance of a Random Predicate. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Johan Håstad |
Randomly supported independence and resistance. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
approximation resistance, k-wise independence |
| 1 | Jakob Nordström, Johan Håstad |
Towards an Optimal Separation of Space and Length in Resolution. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad |
Every 2-csp Allows Nontrivial Approximation. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 68W25, 68Q25 |
| 1 | Johan Håstad, Mats Näslund |
Practical Construction and Analysis of Pseudo-Randomness Primitives. |
J. Cryptology |
2008 |
DBLP DOI BibTeX RDF |
Hard core function, One-way function, Pseudo random generator, Exact security |
| 1 | Jakob Nordström, Johan Håstad |
Towards an Optimal Separation of Space and Length in Resolution |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Jakob Nordström, Johan Håstad |
Towards an optimal separation of space and length in resolution. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
length, lower bound, resolution, space, separation, pebbling, proof complexity |
| 1 | Johan Håstad, Avi Wigderson |
The Randomized Communication Complexity of Set Disjointness. |
Theory of Computing |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Svante Linusson, Johan Wästlund |
A Smaller Sleeping Bag for a Baby Snake. |
Discrete & Computational Geometry |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
The Security of the IAPM and IACBC Modes. |
J. Cryptology |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On the Approximation Resistance of a Random Predicate. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
The square lattice shuffle. |
Random Struct. Algorithms |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On Nontrivial Approximation of CSPs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Subhash Khot |
Query Efficient PCPs with Perfect Completeness. |
Theory of Computing |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Every 2-CSP allows nontrivial approximation. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
approximation algorithms, constraint satisfaction, semi-definite programming |
| 1 | Johan Håstad, Srinivasan Venkatesh |
On the advantage over a random assignment. |
Random Struct. Algorithms |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Mats Näslund |
The security of all RSA and discrete log bits. |
J. ACM |
2004 |
DBLP DOI BibTeX RDF |
RSA-encryption, bit-security, complexity, Cryptography, discrete logarithms |
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Avi Wigderson |
Simple analysis of graph tests for linearity and PCP. |
Random Struct. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Lars Ivansson, Jens Lagergren |
Fitting points on the real line and its application to RH mapping. |
J. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Inapproximability Some history and some open problems. (PDF / PS) |
IEEE Conference on Computational Complexity |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Madhu Sudan |
Hardness of Approximate Hypergraph Coloring. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman |
Combinatorial bounds for list decoding. |
IEEE Transactions on Information Theory |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Srinivasan Venkatesh |
On the advantage over a random assignment. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Gunnar Andersson, Lars Engebretsen, Johan Håstad |
A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p. |
J. Algorithms |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Some optimal inapproximability results. |
J. ACM |
2001 |
DBLP DOI BibTeX RDF |
NP-hard optimization problems, max-sat, linear equations, Inapproximability, probabilistically checkable proofs |
| 1 | Johan Håstad, Svante Linusson, Johan Wästlund |
A Smaller Sleeping Bag for a Baby Snake. |
Discrete & Computational Geometry |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Dor, Johan Håstad, Staffan Ulfberg, Uri Zwick |
On Lower Bounds for Selecting the Median. |
SIAM J. Discrete Math. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
A Slight Sharpening of LMN. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan |
Linear-Consistency Testing. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Mats Näslund |
Practical Construction and Analysis of Pseudo-Randomness Primitives. |
ASIACRYPT |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Subhash Khot |
Query Efficient PCPs with Perfect Completeness. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Avi Wigderson |
Simple Analysis of Graph Tests for Linearity and PCP. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
graph test, pseudorandomness, PCP, Linearity testing, iterated test |
| 1 | Johan Håstad |
On bounded occurrence constraint satisfaction. |
Inf. Process. Lett. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Madhu Sudan |
Hardness of approximate hypergraph coloring |
Electronic Colloquium on Computational Complexity (ECCC) |
2000 |
DBLP BibTeX RDF |
|
| 1 | Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson |
Tight Bounds for Searching a Sorted Array of Strings. |
SIAM J. Comput. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? |
ICALP |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad, Madhu Sudan |
Hardness of Approximate Hypergraph Coloring. |
FOCS |
2000 |
DBLP DOI BibTeX RDF |
approximate hypergraph coloring, covering complexity, probabilistic verifier, PCP verifier, 2-colorable 4-uniform hypergraph, hardness assumption, computational complexity, computational geometry, minimisation, graph colouring, hardness, minimization problems |
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Mats Näslund |
The Security of all RSA and Discrete Log Bits |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan |
Linear Consistency Testing |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad |
On approximating CSP-B |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby |
A Pseudorandom Generator from any One-way Function. |
SIAM J. Comput. |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Gunnar Andersson, Lars Engebretsen, Johan Håstad |
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p. |
SODA |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan |
Linear Consistency Testing. |
RANDOM-APPROX |
1999 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich, Johan Håstad |
On the Complexity of Interactive Proofs with Bounded Communication. |
Inf. Process. Lett. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
The Shrinkage Exponent of de Morgan Formulas is 2. |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikael Goldmann, Johan Håstad |
Monotone Circuits for Connectivity Have Depth (log n)2-o(1). |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Liming Cai, Jianer Chen, Johan Håstad |
Circuit Bottom Fan-In and Computational Power. |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Lars Ivansson, Jens Lagergren |
Fitting Points on the Real Line and Its Application to RH Mapping. |
ESA |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Some Recent Strong Inapproximability Results. |
SWAT |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Mats Näslund |
The Security of Individual RSA Bits. |
FOCS |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Some optimal inapproximability results |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad |
Clique is hard to approximate within n1-epsilon |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Liming Cai, Jianer Chen, Johan Håstad |
Circuit Bottom Fan-in and Computational Power. (PDF / PS) |
IEEE Conference on Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
computational complexity, lower bound, circuit complexity, alternating Turing machine |
| 1 | Johan Håstad |
Some Optimal Inapproximability Results. |
STOC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Johan Håstad |
On the Message Complexity of Interactive Proof Systems |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad, Frank Thomson Leighton, Brian Rogoff |
Analysis of Backoff Protocols for Multiple Access Channels. |
SIAM J. Comput. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan |
Linearity testing in characteristic two. |
IEEE Transactions on Information Theory |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Clique is Hard to Approximate Within n1-epsilon. |
FOCS |
1996 |
DBLP DOI BibTeX RDF |
Max Clique approximation, amortized free bits, global function, local functions, local consistency conditions, computational complexity, polynomial time, proof system |
| 1 | Johan Håstad |
Testing of the Long Code and Hardness for Clique. |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao |
On the Shrinkage Exponent for Read-Once Formulae. |
Theor. Comput. Sci. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Stasys Jukna, Pavel Pudlák |
Top-Down Lower Bounds for Depth-Three Circuits. |
Computational Complexity |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan |
Linearity Testing in Characteristic Two. |
FOCS |
1995 |
DBLP DOI BibTeX RDF |
characteristic two, relative distance, rejection probability, Max3SAT, MaxSNP problems, lower bounds, lower bound, probability, theorem proving, upper bound, homomorphisms, Fourier analysis, Fourier analysis, linearity testing, linear functions |
| 1 | Mikael Goldmann, Johan Håstad |
Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract). |
STOC |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Arne Andersson, Johan Håstad, Ola Petersson |
A tight lower bound for searching a sorted array. |
STOC |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikael Goldmann, Per Grape, Johan Håstad |
On Average Time Hierarchies. |
Inf. Process. Lett. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Ingo Wegener, Norbert Wurm, Sang-Zin Yi |
Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC0. |
Inf. Comput. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On the Size of Weights for Threshold Gates. |
SIAM J. Discrete Math. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Recent Results in Hardness of Approximation. |
SWAT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson |
The complexity of searching a sorted array of strings. |
STOC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Steven Phillips, Shmuel Safra |
A Well-Characterized Approximation Problem. |
Inf. Process. Lett. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Oded Goldreich, Johan Håstad, René Peralta |
Addendum to "Simple Construction of Almost k-wise Independent Random Variables". |
Random Struct. Algorithms |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, A. W. Schrift, Adi Shamir |
The Discrete Logarithm Modulo a Composite Hides O(n) Bits. |
J. Comput. Syst. Sci. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Steven Phillips, Shmuel Safra |
A Well-Characterized Approximation Problem. |
ISTCS |
1993 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad, Stasys Jukna, Pavel Pudlák |
Top-Down Lower Bounds for Depth 3 Circuits |
FOCS |
1993 |
DBLP DOI BibTeX RDF |
nonmonotone circuits, top-down lower bounds, depth 3 circuits, depth 3 AND-OR-NOT circuits, strong lower bound, top-down argument |
| 1 | Johan Håstad |
The shrinkage exponent is 2 |
FOCS |
1993 |
DBLP DOI BibTeX RDF |
shrinkage exponent, random restriction, explicit function, NP |
| 1 | Mikael Goldmann, Johan Håstad |
A Simple Lower Bound for Monotone Clique Using a Communication Game. |
Inf. Process. Lett. |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Oded Goldreich, Johan Håstad, René Peralta |
Simple Construction of Almost k-wise Independent Random Variables. |
Random Struct. Algorithms |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikael Goldmann, Johan Håstad, Alexander A. Razborov |
Majority Gates VS. General Weighted Threshold Gates. |
Computational Complexity |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikael Goldmann, Johan Håstad, Alexander A. Razborov |
Majority Gates vs. General Weighted Threshold Gates. |
Structure in Complexity Theory Conference |
1992 |
DBLP BibTeX RDF |
|
| 1 | William Aiello, Johan Håstad |
Relativized Perfect Zero Knowledge Is Not BPP |
Inf. Comput. |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Mikael Goldmann |
On the Power of Small-Depth Threshold Circuits. |
Computational Complexity |
1991 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")