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: H=aring=stad:Johan
Contributed to:
2014
20142010200920082005200220001997199619951994199019891989198719861985Wrote 21 papers:
- ICALP-v1-2014-BlaisHST #approximate #on the
- On DNF Approximators for Monotone Boolean Functions (EB, JH, RAS, LYT), pp. 235–246.
- STOC-2014-GuruswamiHHSV
- 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.
- STOC-1997-Hastad
- 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.
- STOC-1995-GoldmannH
- 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.