BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
Travelled to:
1 × Denmark
1 × Italy
1 × Switzerland
12 × USA
3 × Canada
Collaborated with:
F.T.Leighton M.Newman A.Andersson O.Petersson V.Guruswami P.Austrin J.Nordström S.Venkatesh M.Goldmann P.Beame A.Shamir S.Kopparty B.Rogoff E.Blais R.A.Servedio L.Tan T.Hagerup P.Harsha S.Srinivasan G.Varma
Talks about:
optim (5) random (4) approxim (3) bound (3) hard (3) code (3) hypercub (2) problem (2) monoton (2) circuit (2)

Person: Johan Håstad

DBLP DBLP: H=aring=stad:Johan

Contributed to:

ICALP (1) 20142014
STOC 20142014
STOC 20102010
STOC 20092009
STOC 20082008
STOC 20052005
STOC 20022002
ICALP 20002000
STOC 19971997
STOC 19961996
STOC 19951995
STOC 19941994
STOC 19901990
ICALP 19891989
STOC 19891989
STOC 19871987
STOC 19861986
STOC 19851985

Wrote 21 papers:

ICALP-v1-2014-BlaisHST #approximate #on the
On DNF Approximators for Monotone Boolean Functions (EB, JH, RAS, LYT), pp. 235–246.
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes (VG, PH, JH, SS, GV), pp. 614–623.
STOC-2010-GuruswamiHK #linear #on the #random
On the list-decodability of random linear codes (VG, JH, SK), pp. 409–416.
STOC-2009-AustrinH #independence
Randomly supported independence and resistance (PA, JH), pp. 483–492.
STOC-2008-NordstromH #towards
Towards an optimal separation of space and length in resolution (JN, JH), pp. 701–710.
STOC-2005-Hastad #approximate
Every 2-CSP allows nontrivial approximation (JH), pp. 740–746.
STOC-2002-HastadV #on the #random
On the advantage over a random assignment (JH, SV), pp. 43–52.
ICALP-2000-Hastad #algorithm #approximate #np-hard #optimisation #performance #problem #question
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? (JH), p. 235.
Some Optimal Inapproximability Results (JH), pp. 1–10.
STOC-1996-Hastad #clique #testing
Testing of the Long Code and Hardness for Clique (JH), pp. 11–19.
STOC-1995-AnderssonHP #array #bound
A tight lower bound for searching a sorted array (AA, JH, OP), pp. 417–426.
Monotone circuits for connectivity have depth (log n)2-o(1) (MG, JH), pp. 569–574.
STOC-1994-AnderssonHHP #array #complexity #string
The complexity of searching a sorted array of strings (AA, TH, JH, OP), pp. 317–325.
STOC-1990-Hastad #generative #pseudo
Pseudo-Random Generators under Uniform Assumptions (JH), pp. 395–404.
ICALP-1989-Hastad #rank
Tensor Rank is NP-Complete (JH), pp. 451–460.
STOC-1989-HastadLN #performance #using
Fast Computation Using Faulty Hypercubes (JH, FTL, MN), pp. 251–263.
STOC-1987-BeameH #bound #problem
Optimal Bounds for Decision Problems on the CRCW PRAM (PB, JH), pp. 83–93.
STOC-1987-HastadLN #configuration management #fault
Reconfiguring a Hypercube in the Presence of Faults (JH, FTL, MN), pp. 274–284.
STOC-1987-HastadLR #analysis #multi #protocol
Analysis of Backoff Protocols for Multiple Access Channels (JH, FTL, BR), pp. 241–253.
STOC-1986-Hastad #bound
Almost Optimal Lower Bounds for Small Depth Circuits (JH), pp. 6–20.
STOC-1985-HastadS #encryption #security
The Cryptographic Security of Truncated Linearly Related Variables (JH, AS), pp. 356–362.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.