检索结果-内蒙古大学图书馆

On the complexity of hardness amplification

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第10期54卷 4575-4586页

作者： Lu, Chi-Jen Tsai, Shi-Chun Wu, Hsin-Lung Acad Sinica Inst Informat Sci Taipei 115 Taiwan Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 30050 Taiwan Natl Taipei Univ Dept Comp Sci & Informat Engn Taipei Taiwan

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.

关键词： computational complexity hardness amplification list-decodable code pseudorandom generator

来源：评论

学校读者我要写书评

暂无评论

Binary codes for Correcting Two Edits

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第10期70卷 6877-6898页

作者： Sun, Yubo Ge, Gennian Capital Normal Univ Sch Math Sci Beijing 100048 Peoples R China

An edit refers to a single insertion, deletion, or substitution. This paper aims to construct binary codes that can correct two edits. To do this, a necessary and sufficient condition for a code to be two-edit correctable is provided, showing that a code is a two-edit correcting code if and only if it can correct two deletions, up to two substitutions, and one deletion and up to one substitution, separately. This criterion allows for the construction of two-edit correcting codes leveraging these three types of error correcting codes. In the field of constructing codes for correcting two deletions, we present a construction with 4 log n + O(log log n) redundant bits that can be viewed as a subcode proposed by Guruswami and Hastad, and provide an alternative proof. Moreover, our two-deletion correcting codes can also correct up to two substitutions after making a slight modification. In the field of constructing codes for correcting one deletion and up to one substitution, we present a construction with 4logn+O(log log n) redundant bits, which outperforms the best previously known results 6 log n + O(1) . Leveraging these codes, we obtain a construction of two-edit correcting codes with 6 log n + O(log log n) redundant bits. This outperforms the best previously known result, which requires at least 8 log n redundant bits. Moreover, we also consider the list-decoding problem under the two-edit channel and construct a two-edit list-decodable code with a list size of two employing 4 log n + O(log log n) redundant bits.

关键词： codes Transforms Germanium Termination of employment Task analysis Redundancy Error correction codes Insertion deletion substitution edit error-correcting code list-decodable code

来源：评论

学校读者我要写书评

暂无评论

On the complexity of hardness amplification

On the complexity of hardness amplification

引用

20th IEEE Annual Conference on Computational Complexity

关键词： computational complexity hardness amplification list-decodable code pseudorandom generator

来源：评论

学校读者我要写书评

暂无评论

SHORT SEED EXTRACTORS AGAINST QUANTUM STORAGE

引用

SIAM JOURNAL ON COMPUTING 2011年第3期40卷 664-677页

作者： Ta-Shma, Amnon Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

In this paper we show that a construction of Trevisan, solving the privacy amplification problem in the classical setting, also solves the problem when the adversary may keep quantum storage, thereby giving the first such construction with logarithmic seed length. The technique we use is a combination of Trevisan's approach of constructing an extractor from a black-box pseudo-random generator, together with locally list-decodable codes and previous work done on quantum random access codes.

关键词： extractors quantum storage random access codes list-decodable code

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：