{"description":"(\u6697\u53f7\u5b66\u7684)\u7591\u4f3c\u4e71\u6570\u751f\u6210\u306e\u8a71. \u8a3c\u660e\u306e\u624b\u6cd5\u3068\u3057\u3066\u306f, \u8b58\u5225\u6a5f\u304c\u5b58\u5728\u3059\u308b\u3068, \u4e00\u65b9\u5411\u6027\u304c\u7834\u308c\u308b\u3053\u3068\u3092\u8a00\u3046. HSS\u3068\u304bGR\u306f\u3053\u306e\u4e00\u7a2e\u304b. hard-core predicate (function)\u3092\u4f5c\u308b Blum-Blum-Shub\u3068\u304bGoldreich-Levin\u3068\u304b. List-decoding\u3068\u95a2\u4fc2\u3057\u3066\u304f\u308b. \u30d5\u30fc\u30ea\u30a8\u5909\u63db+List-decoding\u306b\u306a\u308b\uff08\u3089\u3057\u3044\uff09. \u4e00\u65b9\u5411\u6027\u3092\u8a00\u3063\u3066\u304a\u304f. \u306e\u3061, \u8b58\u5225\u6a5f\u304c\u5b58\u5728\u3059\u308b\u3068, \u4e00\u65b9\u5411\u6027\u304b\u3089\u8a00\u3048\u308bhard-core predicate\u304c\u7834\u308c\u308b\u3053\u3068\u3092\u793a\u3059. Impagliazzo-Naor \u304f\u3089\u3044\u304b. 2, 3\u304c\u30c0\u30e1\u3060\u3063\u305f\u306e\u3067, 1\u306b\u623b\u3057\u3066\u307f\u308b.","version":"1.0","provider_url":"https://hatena.blog","width":"100%","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20060904%2F1157373999\" title=\" - 186 @ hatenablog\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","image_url":null,"type":"rich","author_url":"https://blog.hatena.ne.jp/smoking186/","categories":["study"],"published":"2006-09-04 21:46:39","author_name":"smoking186","height":"190","provider_name":"Hatena Blog","url":"https://186.hatenablog.com/entry/20060904/1157373999","title":"","blog_title":"186 @ hatenablog","blog_url":"https://186.hatenablog.com/"}