On the complexity of hardness amplification
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
4586 | en_US |
dc.citation.issue |
10 | en_US |
dc.citation.spage |
4575 | en_US |
dc.citation.volume |
54 | en_US |
dc.contributor.author |
Lu, Chi-Jen | en_US |
dc.contributor.author |
Tsai, Shi-Chun | en_US |
dc.contributor.author |
Wu, Hsin-Lung | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:42:24Z | |
dc.date.available |
2014-12-08T15:42:24Z | |
dc.date.issued |
2008-10-01 | en_US |
dc.description.abstract |
For delta is an element of (0, 1) and k, n is an element of N, we study the task of transforming a hard function f : {0, 1}(n) -> {0, 1}, with which any small circuit disagrees on (1 - delta)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1 - delta(k))/2 fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size 2(o(k1/d)) or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth) for any delta is an element of (0, 1). This extends the result of Viola, which only works when (1 - delta)/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f', even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with Omega(k log(1/delta)) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1 - delta)/2 = 2(-n). Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory. | en_US |
dc.identifier.doi |
10.1109/TIT.2008.928988 | en_US |
dc.identifier.issn |
0018-9448 | en_US |
dc.identifier.journal |
IEEE TRANSACTIONS ON INFORMATION THEORY | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1109/TIT.2008.928988 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/28798 | |
dc.identifier.wosnumber |
WOS:000259407000012 | |
dc.language.iso |
en_US | en_US |
dc.subject |
computational complexity | en_US |
dc.subject |
hardness amplification | en_US |
dc.subject |
list-decodable code | en_US |
dc.subject |
pseudorandom generator | en_US |
dc.title |
On the complexity of hardness amplification | en_US |
dc.type |
Article; Proceedings Paper | en_US |
檔案
- 000259407000012.pdf (375.7 KB, Adobe PDF)
所屬典藏: 會議論文