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

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chung, Kai-Min Guo, Siyao Liu, Qipeng Qian, Luowen Acad Sinica Inst Informat Sci Taipei Taiwan New York Univ Shanghai Dept Comp Sci Shanghai Peoples R China Princeton Univ Dept Comp Sci Princeton NJ 08544 USA NTT Res Princeton NJ USA Boston Univ Dept Comp Sci 111 Cummington St Boston MA 02215 USA

ISBN: (纸本)9781728196213

In function inversion, we are given a function f : [N] (sic) [N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of ST2 = (Omega) over tilde (N) for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time (Omega) over tilde(root N/S). Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains ST2 = (Omega) over tilde (N). In this work, we prove that even with quantum advice, ST + T-2 = (N) is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for S = (Omega) over tilde (v N), ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). Salted cryptography: We show that "salting generically provably defeats preprocessing," a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in

关键词： space tradeoffs quantum computation quantum query complexity quantum advice post-quantum cryptography function inversion

来源：评论

学校读者我要写书评

暂无评论

Mobius transformation in generalized evidence theory

引用

APPLIED INTELLIGENCE 2022年第7期52卷 7818-7831页

作者： Xue, Yige Deng, Yong Univ Elect Sci & Technol China Inst Fundamental & Frontier Sci Chengdu 610054 Peoples R China Shaanxi Normal Univ Sch Educt Xian 710062 Peoples R China Japan Adv Inst Sci & Technol Sch Knowledge Sci Nomi Ishikawa 9231211 Japan

Mobius transformation is a very important information inversion tool. Mobius transformation is sought after by many experts and scholars at home and abroad, and is a hot research topic at present. Mobius transformation can use the known information to reverse the unknown information, indicating that it has a strong ability to process information. Generalized evidence theory is an extension of classical evidence theory. When belief degree of the null subset is 0, then the generalized evidence theory will be degenerated as classical Dempster-Shafer evidence theory. However, how to apply Mobius transformation to generalized evidence theory is still an open problem. This paper proposes Mobius transformation in generalized evidence theory, which can perform function inversion of generalized evidence theory effectively. Numerical examples are used to prove the validity of Mobius transformation in generalized evidence theory. The experimental results show that the Mobius transformation in generalized evidence theory can effectively invert the generalized evidence theory and is a very effective function inversion method.

关键词： Mobius transformation function inversion Dempster-Shafer evidence theory Generalized evidence theory

来源：评论

学校读者我要写书评

暂无评论

On the Existence Problem of Finite Bases of Identities in the Algebras of Recursive functions

引用

AUTOMATIC CONTROL AND COMPUTER SCIENCES 2021年第7期55卷 702-711页

作者： Sokolov, V. A. Demidov Yaroslavl State Univ 14 Sovetskaya Yaroslavl 150003 Russia

Raphael Robinson showed that all primitive recursive functions, depending on one argument, and only they could be obtained from two functions s(x) = x + 1 and q(x) = x divided by [root x](2) by using the operations of addition+, superposition*, and iteration i. Julia Robinson proved that, starting from the same two functions and using the operations of addition+, superposition*, and the operation(-1) of function inversion, one could obtain all general recursive functions (under a certain condition on the inversion operation) and all partial recursive functions. On the basis of these results, A.I. Mal'tsev introduced into consideration Raphael Robinson algebra of all unary primitive recursive functions and two of Julia Robinson's algebras: namely, the partial algebra of all unary general recursive functions and the algebra of all unary partial recursive functions, and proposed to study the properties of these algebras, including the existence of finite bases of identities in these algebras. In this paper, we show that there is no finite basis of identities in any of the above algebras.

关键词： algebras recursive functions identities basis superposition iteration function inversion

来源：评论

学校读者我要写书评

暂无评论

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False 15

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogor...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Mazor, Noam Pass, Rafael Cornell Tech New York NY 10044 USA Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9783959773096

The Perebor (Russian for "brute-force search") conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP P conjecture (which they predate) and state that for "meta-complexity" problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search. In this paper, we disprove the non-uniform version of the Perebor conjecture for the Time Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t("), there exists of a circuit of size 24/5 (.) that solves the t(.)-bounded Kolmogorov complexity problem on every instance. Our algorithm is black-box in the description of the Universal Turing Machine U employed in the definition of Kolmogorov Complexity and leverages the characterization of one-way functions through the hardness of the time-bounded Kolmogorov complexity problem of Liu and Pass (FOCS'20), and the time-space trade-off for one-way functions of Fiat and Naor (STOC'91). We additionally demonstrate that no such black-box algorithm can have circuit size smaller than 2'0 '("'). Along the way (and of independent interest), we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size 24'/5 (');as far as we know, this yields the first formal proof that a non-trivial circuit can invert any efficient function.

关键词： Kolmogorov complexity perebor conjecture function inversion

来源：评论

学校读者我要写书评

暂无评论

Beating Brute Force for Compression Problems 2024

Beating Brute Force for Compression Problems

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Hirahara, Shuichi Ilango, Rahul Williams, R. Ryan Natl Inst Informat Tokyo Japan MIT Cambridge MA USA

ISBN: (纸本)9798400703836

A compression problem is defined with respect to an efficient encoding function 5;given a string G, our task is to find the shortest y such that f (y) = G. The obvious brute-force algorithm for solving this compression task on n-bit strings runs in time O(2(l) center dot t(n)), where l is the length of the shortest description y and t(n) is the time complexity of 5 when it prints n-bit output. We prove that every compression problem has a Boolean circuit family which finds short descriptions more eficiently than brute force. In particular, our circuits have size 2(4l/5) center dot poly(t(n)), which is significantly more efficient for all l >> logt(n)). Our construction builds on Fiat-Naor's data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length. As a consequence, the Minimum Circuit Size Problem for generic fan-in two circuits of size s(n) on truth tables of size 2(n) can be solved by circuits of size 2(4/5) (center dot) (w+o (w)) center dot poly(2(n)), where w = s(n) log(2)(s(n) + n). This improves over the brute-force approach of trying all possible size-s(n) circuits for all s(n) >= n. Similarly, the task of computing a short description of a string x when its K-t-complexity is at most l, has circuits of size 2(4/5l) center dot poly(t). We also give non-trivial circuits for computing Kt complexity on average, and for solving NP relations with "compressible" instance-witness pairs.

关键词： compression circuit complexity function inversion

来源：评论

学校读者我要写书评

暂无评论

EVALUATION AND inversion OF THE RATIOS OF MODIFIED BESSEL-functionS, I1(X)-I0(X) AND I1.5(X)-I0.5(X)

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 1981年第2期7卷 199-208页

作者： HILL, GW Division of Mineral Chemistry CSIRO Port Melbourne Australia 3207

Adaptation to specific processor precision is illustrated for procedures for evaluating the ratios A(k) = I1(k)/Io(k) and B(k) = 115(K)/I05(K), which provide the expected value R of the mean modulus of random umt vectors, distributed with concentration parameter k in (a) von Mises’ distribution of directions m two dimensmns (on a circle) or (b) Fisher's chstribution in three dnnensions (on a sphere), respectively. For large k, the exponential equivalent of B(k) = coth k - 1/K is used. Three continued fractmn expansmns are shown to be statable for recurswe evaluatmn from a depth of recursion n(k | S), approximated to ensure at least S significant decimal chgits m the result. Improved approximatmns for the inverse functions A-1(R) and B-1(R) provide maxunum likelihood estimates of K for gaven R, directly achmvmg at least 3S and 8S, respectively, which may be extended near processor preclsmn by few Newton-Raphson improvements. © 1981, ACM. All rights reserved.

关键词： approximation backward recursmn contmued fractmns Fisher distribution function inversion modified Bessel functmn ratio Newton-Raphson yon Mises distributmn

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：