Complexity of Hard-Core Set Proofs |
| |
Authors: | Chi-Jen Lu Shi-Chun Tsai Hsin-Lung Wu |
| |
Affiliation: | 1. Institute of Information Science, Academia Sinica, Taipei, Taiwan 2. Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 3. Department of Computer Science and Information Engineering, National Taipei University, Taipei, Taiwan
|
| |
Abstract: | We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function f:{0,1}n?{0,1}{f:\{0,1\}^n\to\{0,1\}} which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of inputs. Then, the hard-core set lemma says that f must have a hard-core set H of density δ on which it is “extremely hard”, in the sense that any circuit of size
s¢=O(s/(\frac1e2log(\frac1ed))){s'=O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))} must disagree with f on at least (1-e)/2{(1-\epsilon)/2} fraction of inputs from H. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|