Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
[1]
Hilfe
Suche: Author="H{\aa}stad, Johan"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
On DNF approximators for monotone Boolean functions
Eric Blais
,
Johan Håstad
,
Rocco A. Servedio
,
Li-Yang Tan
Lecture Notes in Computer Science
8572
, 2014, pp. 235-246
On the NP-hardness of Max-Not-2
Johan Håstad
SIAM Journal on Computing
43
(1), 2014, pp. 179-193
On the correlation of parity and small-depth circuits
Johan Håstad
SIAM Journal on Computing
43
(5), 2014, pp. 1699-1708
Randomly supported independence and resistance
Per Austrin
,
Johan Håstad
SIAM Journal on Computing
40
(1), 2011, pp. 1-27
Beating the random ordering is hard: Every ordering CSP is approximation resistant
Venkatesan Guruswami
,
Johan Håstad
,
Rajsekar Manokaran
,
Prasad Raghavendra
,
Moses Charikar
SIAM Journal on Computing
40
(3), 2011, pp. 878-914
On the list-decodability of random linear codes
Venkatesan Guruswami
,
Johan Håstad
,
Swastik Kopparty
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC'2010 (Cambridge, Massachusetts, June 5-8, 2010)
, 2010, pp. 409-416
Randomly supported independence and resistance
Per Austrin
,
Johan Håstad
Proceedings of the 41st International ACM Symposium on Theory of Computing, STOC'2009 (Bethesda, Maryland, USA, May 31 - June 2, 2009)
, 2009, pp. 483-492
Towards an optimal separation of space and length in resolution
Jakob Nordström
,
Johan Håstad
Proceedings of the 40th International ACM Symposium on Theory of Computing, STOC'2008 (Victoria, BC, Canada, May 17-20, 2008)
, 2008, pp. 701-710
Every 2-CSP allows nontrivial approximation
Johan Håstad
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC'2005 (Baltimore, Maryland, USA, May 22-24, 2005)
, 2005, pp. 740-746
The security of all RSA and discrete log bits
Johan Håstad
,
Mats Näslund
Journal of the ACM
51
(2), 2004, pp. 187-230
Fitting points on the real line and its application to RH mapping
Johan Håstad
,
Lars Ivansson
,
Jens Lagergren
Journal of Algorithms
49
(1), 2003, pp. 42-62
Hardness of approximate hypergraph coloring
Venkatesan Guruswami
,
Johan Håstad
,
Madhu Sudan
SIAM Journal on Computing
31
(6), 2002, pp. 1663-1686
On the advantage over a random assignment
Johan Håstad
,
S. Venkatesh
Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC'2002 (Montreal, Quebec, Canada, May 19-21, 2002)
, 2002, pp. 43-52
A new way of using semidefinite programming with applications to linear equations mod
p
Gunnar Andersson
,
Lars Engebretsen
,
Johan Håstad
Journal of Algorithms
39
(2), 2001, pp. 162-204
Linear-constistency testing
Yonatan Aumann
,
Johan Håstad
,
Michael O. Rabin
,
Madhu Sudan
Journal of Computer and System Sciences
62
(4), 2001, pp. 589-607
On lower bounds for selecting the median
Dorit Dor
,
Johan Håstad
,
Staffan Ulfberg
,
Uri Zwick
SIAM Journal on Discrete Mathematics
14
(3), 2001, pp. 299-311
Some optimal inapproximability results
Johan Håstad
Journal of the ACM
48
(4), 2001, pp. 798-859
A slight sharpening of LMN
Johan Håstad
Journal of Computer and System Sciences
63
(3), 2001, pp. 498-508
Tight bounds for searching a sorted array of strings
Arne Andersson
,
Torben Hagerup
,
Johan Håstad
,
Ola Petersson
SIAM Journal on Computing
30
(5), 2000, pp. 1552-1578
Simple analysis of graph tests for linearity and PCP
Johan HÅstad
,
Avi Wigderson
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, CCC'2001 (Chicago, Illinois, June 18-21, 2001)
, 2000, pp. 244-254
On bounded occurrence constraint satisfaction
Johan Håstad
Information Processing Letters
74
(1-2), 2000, pp. 1-6
A new way to use semidefinite programming with applications to linear equations mod
p
Gunnar Andersson
,
Lars Engebretsen
,
Johan Håstad
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'99 (Baltimore, Maryland, January 17-19, 1999)
, 1999, pp. 41-50
Linear consistency testing
Yonatan Aumann
,
Johan Håstad
,
Michael O. Rabin
,
Madhu Sudan
Lecture Notes in Computer Science
1671
, 1999, pp. 109-120
A pseudorandom generator from any one-way function
Johan Håstad
,
Russell Impagliazzo
,
Leonid A. Levin
,
Michael Luby
SIAM Journal on Computing
28
(4), 1999, pp. 1364-1396
The security of all RSA and discrete log bits
Johan Håstad
,
Mats Näslund
Technical Report (TR99-037), 1999
Seiten 1
2
3
>