P138
Clique is hard to approximate within n/sup 1-ε/Some optimal inapproximability resultsA simple lower bound for monotone clique using a communication gameClique is hard to approximate within n1−εMaking the Long Code ShorterThe square lattice shuffle, correctionErratum: Polynomial Time Algorithms for Finding Integer Relations Among Real NumbersOn DNF Approximators for Monotone Boolean FunctionsOn the Correlation of Parity and Small-Depth CircuitsOn the NP-Hardness of Max-Not-2Super-polylogarithmic hypergraph coloring hardness via low-degree long codesOn the power of many one-bit proversOn the usefulness of predicatesApproximating Linear Threshold PredicatesOn the NP-Hardness of Max-Not-2Satisfying Degree-d Equations over GF[2] nAn Efficient Parallel Repetition TheoremApproximating Linear Threshold PredicatesSpecial Issue “Conference on Computational Complexity 2009” Guest Editor’s ForewordOn the Approximation Resistance of a Random PredicateRandomly supported independence and resistanceEvery 2-csp Allows Nontrivial ApproximationPractical Construction and Analysis of Pseudo-Randomness PrimitivesA Smaller Sleeping Bag for a Baby SnakeThe square lattice shuffleComplexity Theory, Proofs and ApproximationOn the advantage over a random assignmentThe security of all RSA and discrete log bitsFitting points on the real line and its application to RH mappingSimple analysis of graph tests for linearity and PCPHardness of Approximate Hypergraph ColoringA New Way of Using Semidefinite Programming with Applications to Linear Equations mod pA Slight Sharpening of LMNA Smaller Sleeping Bag for a Baby SnakeLinear-Consistency TestingOn Lower Bounds for Selecting the MedianOn bounded occurrence constraint satisfactionTight Bounds for Searching a Sorted Array of StringsCircuit Bottom Fan-in and Computational PowerMonotone Circuits for Connectivity Have Depth (log n)2-o(1)
P50
Q29013362-2ec9650d-4c3d-614a-5605-1bb12aac7189Q55879781-39AE55F4-E7FD-4883-838A-ADE61FBE9F7AQ56210414-D90D87AE-7C04-4BFF-8B5F-B1DBBA0278DCQ56210419-C833102C-DC22-4BC0-B0B1-73A7A73617A2Q56958711-AB002479-D145-4DE4-9223-F5AF1FAB2D2AQ56958717-161C8E32-CC93-45A1-95D3-06CA794236D3Q56958732-4DEBC256-A928-4A93-A32B-0E7A9F4153F8Q56958740-C18B60FD-6559-44E5-B2CD-A27F14F04B32Q56958749-968EBD40-228D-44B9-A664-97FDBB27E181Q56958755-691B9A56-27D7-4CF5-9099-18985644D100Q56958759-7ACE563D-6CA4-4BB6-9FD5-91CABF96573BQ56958765-D89F64C5-7C3D-4040-BE60-D81B4023949EQ56958773-ADEABACF-DBD4-49E4-8172-20B2195A5E39Q56958782-BD16878B-1A4D-4E73-A312-E8430F0E6E83Q56958799-37E37427-467B-474A-93F3-05B5DD47FED1Q56958844-B7CA46F4-363F-4187-B01B-60AA4F7F5892Q56958852-39431AB7-4BF7-4A6A-BB9B-BF69320FD70FQ56958859-1CDE08F9-3FC7-4711-8C4F-1D4A108F56B8Q56958868-BBF9791C-488D-4C1D-85F4-07DD839FCB63Q56958874-3C3EEBD2-8E1A-4804-91AB-B629F177B7E0Q56958884-3DA217B3-AD90-4CD4-9275-2254D61168D3Q56958890-A58BAEF6-5A56-4A3C-9EC9-AC7C778C94B9Q56958898-406E91D4-B659-4489-B978-861B0032ADE9Q56958907-C924952E-D25C-4B6D-A6E7-B0F33AE1A392Q56958922-139DF835-FC88-479C-AC37-D9B3B425EC17Q56958926-2FE0CB68-B17F-4C99-99C2-0B86ADB0BCBAQ56958935-A7EA8368-4CEB-456F-9AFC-3FF5DDFE0BB8Q56958944-CFE3A54E-2181-4292-B03F-FFB48096FE5DQ56958958-2E0B35F5-ABE2-48DC-93CA-77BF9ADDDF25Q56958974-4758131F-E21A-41EA-9F67-0313F412C0CBQ56958987-0ad7962f-4368-1c60-8603-dc8eccbb59d8Q56958995-EB8A1F19-F7AA-41BF-B80E-4E7552382A20Q56959003-7337D40C-45F6-4F03-8E17-DD7455B861BDQ56959009-67CB213F-90E9-4F2E-851B-B0E1483BE4CCQ56959015-28FA8901-96D0-4A60-80DF-15AA5561CA7AQ56959022-85F6F1AA-4B9F-4B17-A6CB-9F7FE09546D6Q56959043-B659F3FF-CFB4-425A-98E3-AB06579200AFQ56959054-42A3ED66-CEB5-4AC1-B7A7-A712117C62C5Q56959065-FC599F7D-0499-4DF1-876A-380B0348D3AFQ56959071-F64C32E3-F2E6-48A4-B7D6-66A24D5590C7
P50
description
Swedish computer scientist
@en
Zweeds wiskundige
@nl
ríomheolaí Sualannach
@ga
schwedischer Informatiker
@de
svensk matematikar, informatikar og ingeniør
@nn
svensk matematiker, datavetare och ingenjör
@sv
svensk matematiker, informatiker og ingeniør
@da
svensk matematiker, informatiker og ingeniør
@nb
ریاضیدان، دانشمند علوم کامپیوتر، و مهندس سوئدی
@fa
ಗಣಿತಜ್ಞ
@kn
name
Johan Håstad
@ast
Johan Håstad
@ca
Johan Håstad
@da
Johan Håstad
@de
Johan Håstad
@en
Johan Håstad
@es
Johan Håstad
@fi
Johan Håstad
@fr
Johan Håstad
@ga
Johan Håstad
@mg
type
label
Johan Håstad
@ast
Johan Håstad
@ca
Johan Håstad
@da
Johan Håstad
@de
Johan Håstad
@en
Johan Håstad
@es
Johan Håstad
@fi
Johan Håstad
@fr
Johan Håstad
@ga
Johan Håstad
@mg
altLabel
Håstad
@de
Håstad
@sv
Johan Hastad
@de
Johan Hastad
@es
Johan Hastad
@fr
Johan Hastad
@nl
Johan Torkel Håstad
@en
prefLabel
Johan Håstad
@ast
Johan Håstad
@ca
Johan Håstad
@da
Johan Håstad
@de
Johan Håstad
@en
Johan Håstad
@es
Johan Håstad
@fi
Johan Håstad
@fr
Johan Håstad
@ga
Johan Håstad
@mg