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

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Ilango, Rahul Ren, Hanlin Santhanam, Rahul MIT Cambridge MA 02139 USA Univ Oxford Oxford England Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450392648

We show broad equivalences in the average-case complexity of many different meta-complexity problems, including Kolmogorov complexity, time-bounded Kolmogorov complexity, and the Minimum Circuit Size Problem. These results hold for a wide range of parameters (various thresholds, approximation gaps, weak or strong average-case hardness, etc.) and complexity notions, showing the theory of meta-complexity is very robust in the average-case setting. Our results are shown by establishing new and generic connections between meta-complexity and the theory of pseudorandomness and one-way functions. Using these connections, we give the first unconditional characterization of one-way functions based on the average-case hardness of the Minimum Circuit Size Problem. We also give a surprising and clean characterization of one-way functions based on the average-case hardness of (the worst-case uncomputable) Kolmogorov complexity. Moreover, the latter is the first characterization of one-way functions based on the averagecase hardness of a fixed problem on any samplable distribution. We give various applications of these results to the foundations of cryptography and the theory of meta-complexity. For example, we show that the average-case hardness of deciding k-SAT or Clique on any samplable distribution of high enough entropy implies the existence of one-way functions. We also use our results to unconditionally solve various meta-complexity problems in CZK (computational zero-knowledge) on average, and give implications of our results for the classic question of proving NP-hardness for the Minimum Circuit Size Problem.

关键词： meta-complexity average-case complexity coding theorem minimum circuit size problem Kolmogorov complexity one-way functions

来源：评论

学校读者我要写书评

暂无评论

Capturing One-Way Functions via NP-Hardness of meta-complexity 2023

Capturing One-Way Functions via NP-Hardness of Meta-Complexi...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Hirahara, Shuichi Natl Inst Informat Tokyo Japan

ISBN: (纸本)9781450399135

A one-way function is a function that is easy to compute but hard to invert on average. We establish the first characterization of a one-way function by worst-case hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way function. Specifically, we generalize the notion of time-bounded conditional Kolmogorov complexity to distributional Kolmogorov complexity, and prove that a one-way function exists if and only if it is NP-hard to approximate the distributional Kolmogorov complexity under randomized polynomial-time reductions and NP is hard in the worst case. We also propose the meta-complexity Padding Conjecture, which postulates that distributional Kolmogorov complexity is paddable by an approximation-preserving reduction. Under this conjecture, we prove that the worst-case hardness of an approximate version of the Minimum Circuit Size Problem characterizes the existence of a one-way function. Our results extend the emerging paradigm of meta-complexity, which suggests that proving NP-hardness of meta-computational problems (i.e., problems that ask to compute complexity) is sufficient to exclude errorless Heuristica and error-prone Pessiland from Impagliazzo's five worlds. The key technical contribution is to conditionally close the gap between errorless and error-prone average-case complexities by combining Nanashima's proof techniques of showing "limits" of black-box reductions (ITCS'21) with non-black-box worst-case-to-average-case reductions of Hirahara (FOCS'18).

关键词： one-way functions meta-complexity distributional Kolmogorov complexity

来源：评论

学校读者我要写书评

暂无评论

NP-Hardness of Approximating meta-complexity: A Cryptographic Approach 2023

NP-Hardness of Approximating Meta-Complexity: A Cryptographi...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Huang, Yizhi Ilango, Rahul Ren, Hanlin Tsinghua Univ IIIS Beijing Peoples R China MIT Cambridge MA USA Univ Oxford Oxford England

ISBN: (纸本)9781450399135

It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation. In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use cryptographic constructions in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows. 1. Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity (K-dagger (x vertical bar y)) in the regime where t >> vertical bar y vertical bar. Previously, the best hardness of approximation known was a vertical bar x vertical bar(1/poly(log log vertical bar x vertical bar)) factor and only in the sublinear regime (t << vertical bar y vertical bar). 2. Unconditionally, we show that for any constant c > 1, the Minimum Oracle Circuit Size Problem (MOCSP) is NP-hard to approximate, where Yes instances have circuit complexity at most s, and No instances have circuit complexity at least S-C. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC'13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity s versus 10s log N. 3. Finally, we define a "multi-valued" version of MCSP, called mvMCSP, and show that w.p. 1 over a random oracle O, it is NP-hard to approximate mvMCSP(O). under quasi-polynomial-time reductions with an.. oracle. Intriguingly, this result follows almost directly from the security of Micali's CS Proofs (Micali, SICOMP'00). In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in p

关键词： meta-complexity Minimum Circuit Size Problem cryptography witness encryption NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions 2021

Average-Case Hardness of NP from Exponential Worst-Case Hard...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Hirahara, Shuichi Natl Inst Informat Tokyo Japan

ISBN: (纸本)9781450380539

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this question has been discussed from various perspectives based on technical barrier results, such as the limits of black-box reductions and the non-existence of worst-case hardness amplification procedures in PH. In this paper, we overcome these barriers and resolve the open question by presenting the following main results: 1. UP not subset of DTIME(2(O(n/log n))) implies DistNP not subset of AvgP. 2. PH not subset of DTIME(2(O(n/log n))) implies DistPH not subset of AvgP. 3. NP not subset of DTIME(2(O(n/log n))) implies DistNP not subset of Avg(P)P. Here, Avg(P)P denotes P-computable average-case polynomial time, which interpolates average-case polynomial-time and worst-case polynomial-time. We complement this result by showing that DistPH not subset of AvgP if and only if DistPH not subset of Avg(P)P. At the core of all of our results is a new notion of universal heuristic scheme, whose running time is P-computable average-case polynomial time under every polynomial-time samplable distribution. Our proofs are based on the meta-complexity of time-bounded Kolmogorov complexity: We analyze average-case complexity through the lens of worst-case meta-complexity using a new "algorithmic" proof of language compression and weak symmetry of information for time-bounded Kolmogorov complexity.

关键词： average-case complexity meta-complexity time-bounded Kolmogorov complexity pseudorandomness computational depth

来源：评论

学校读者我要写书评

暂无评论

The Minimum Formula Size Problem is (ETH) Hard 62

The Minimum Formula Size Problem is (ETH) Hard

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Ilango, Rahul MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781665420556

A longstanding open question is whether the Minimum Circuit Size Problem (MCSP) is NP-complete. In fact, even determining whether MCSP has a search-to-decision reduction has been open for over twenty years. We show that, under the Exponential Time Hypothesis, the Minimum (DeMorgan) Formula Size Problem, MFSP, is not in P. Building on this, we show that MFSP has a polynomial-time (exact) search-to-decision reduction, a result that does not relativize. Our main technique relates the formula complexity of a partial function with the formula complexity of an associated total function and is proved using the "leaf weighting" technique of Buchfuhrer and Umans.

关键词： Minimum Formula Size Problem Minimum Circuit Size Problem Boolean Formulas meta-complexity

来源：评论

学校读者我要写书评

暂无评论

Optimal Coding for Randomized Kolmogorov complexity and Its Applications 65

Optimal Coding for Randomized Kolmogorov Complexity and Its ...

引用

65th Symposium on Foundations of Computer Science

作者： Hirahara, Shuichi Lu, Zhenjian Nanashima, Mikito Natl Inst Informat Tokyo Japan Univ Warwick Coventry W Midlands England Tokyo Inst Technol Tokyo Japan

ISBN: (纸本)9798331516758;9798331516741

The coding theorem for Kolmogorov complexity states that any string sampled from a computable distribution has a description length close to its information content. A coding theorem for resource-bounded Kolmogorov complexity is the key to obtaining fundamental results in average-case complexity, yet whether any samplable distribution admits a coding theorem for randomized time-bounded Kolmogorov complexity (rK(poly)) is open and a common bottleneck in the recent literature of meta-complexity. Previous works bypassed this issue by considering probabilistic Kolmogorov complexity (pK(poly)), in which public random bits are assumed to be available. In this paper, we present an efficient coding theorem for randomized Kolmogorov complexity under the non-existence of one-way functions, thereby removing the common bottleneck. This enables us to prove rK(poly) counterparts of virtually all the average-case results that were proved only for pK(poly), and enables the resolution of the following concrete open problems. 1) The existence of a one-way function is characterized by the failure of average-case symmetry of information for randomized time-bounded Kolmogorov complexity, as well as a conditional coding theorem for randomized time-bounded Kolmogorov complexity. This resolves the open problem of Hirahara, Ilango, Lu, Nanashima, and Oliveira (STOC'23). 2) Hirahara, Kabanets, Lu, and Oliveira (CCC'24) showed that randomized time-bounded Kolmogorov complexity admits search-to-decision reductions in the errorless average-case setting over any samplable distribution, and left open whether a similar result holds in the error-prone setting. We resolve this question affirmatively, and as a consequence, characterize the existence of a one-way function by the average-case hardness of computing rK(poly) with respect to an arbitrary samplable distribution, which is an rK(poly) analogue of the pK(poly) characterization of Liu and Pass (CRYPTO'23). The key technical lemma is that any d

关键词： Kolmogorov complexity coding theorem one-way functions symmetry of information meta-complexity

来源：评论

学校读者我要写书评

暂无评论

Excluding PH Pessiland 13

Excluding PH Pessiland

引用

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： Hirahara, Shuichi Santhanam, Rahul Principle of Informatics Research Division National Institute of Informatics Tokyo Japan Department of Computer Science University of Oxford United Kingdom

ISBN: (纸本)9783959772174

Heuristica and Pessiland are "worlds" of average-case complexity [Impagliazzo95] that are considered unlikely but that current techniques are unable to rule out. Recently, [Hirahara20] considered a PH (Polynomial Hierarchy) analogue of Heuristica, and showed that to rule it out, it would be sufficient to prove the NP-completeness of the problem GapMINKTPH of estimating the PH-oracle time-bounded Kolmogorov complexity of a string. In this work, we analogously define "PH Pessiland" to be a world where PH is hard on average but PH-computable pseudo-random generators do not exist. We unconditionally rule out PH-Pessiland in both non-uniform and uniform settings, by showing that the distributional problem of computing PH-oracle time-bounded Kolmogorov complexity of a string over the uniform distribution is complete for an (error-prone) average-case analogue of PH. Moreover, we show the equivalence between error-prone average-case hardness of PH and the existence of PH-computable pseudorandom generators. © Shuichi Hirahara and Rahul Santhanam;licensed under Creative Commons License CC-BY 4.0

关键词： Average-case complexity meta-complexity Pseudorandomness

来源：评论

学校读者我要写书评

暂无评论

Non-Disjoint Promise Problems from meta-Computational View of Pseudorandom Generator Constructions

引用

THEORY OF COMPUTING 2023年 19卷

作者： Hirahara, Shuichi Natl Inst Informat Principles Informat Res Div Tokyo Japan

The standard notion of promise problem is a pair of disjoint sets of instances, each of which is regarded as YEs and No instances, respectively, and the task of solving a promise problem is to distinguish these two sets of instances. In this paper, we introduce a set of new promise problems which are conjectured to be non-disjoint, and prove that hardness of these "non-disjoint" promise problems gives rise to the existence of hitting set generators (and vice versa). We do this by presenting a general principle which converts any black-box construction of a pseudorandom generator into the existence of a hitting set generator whose security is based on hardness of some "non-disjoint" promise problem (via a non-black-box security reduction).Applying the principle to cryptographic pseudorandom generators, we introduce the Gap(K-SAT vs K) problem, which asks to distinguish strings whose time-bounded SAT-oracle Kolmogorov complexity is small from strings whose time-bounded Kolmogorov complexity (without SAT oracle) is large. We show that if this problem is NP-hard, the worst-case and average-case complexities of PH are equivalent. This generalizes the non-black-box worst-case to average-case reductions of Hirahara (FOCS'18) and improve the approximation error from O(./n) to O(log n).Applying the principle to complexity-theoretic pseudorandom generators, we introduce a family of meta-computational Circuit Lower-bound Problems (MCLPs), which are problems of distinguishing the truth tables of explicit functions from hard functions. Our results generalize the hardness versus randomness framework and identify problems whose circuit lower bounds characterize the existence of hitting set *** also establish the equivalence between the existence of a non-trivial derandomization algorithm for uniform algorithms and a uniform lower bound for a problem of approximating Levin's Kt-complexity.

关键词： pseudorandom generator hitting set generator meta-complexity Levin's Kt complexity minimum circuit size problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：