Generative Models of Huge Objects

Lunjia Hu, Inbal Livni-Navon, Omer Reingold

Stanford University

巨大对象的生成模型

要点：

这项工作启动了对显式分布的系统研究，这些显式分布与单个指数大小的组合对象无法区分。在此，文章扩展了Goldreich、Goldwasser和Nussboim（SICOMP 2010）的工作，他们专注于实现与均匀分布无法区分的巨大对象，满足一些全球财产（他们创造了真实性）。学习理论中的生成模型和图论中的正则引理的研究激发了单个对象的不可分辨性。在伪随机性的设置中很好理解的问题存在着重大挑战，在考虑巨大对象的生成模型时有时是不可能的。

一句话总结：

通过在几个自然环境中为巨大的不可区分对象提供一个学习算法来证明这项研究的通用性，这些自然环境包括：对函数中的个数或图中边的个数具有真实性要求的稠密函数和图，以及满足某些全局财产的稀疏图的弱正则性引理的一个版本。这些和其他结果概括了基本伪随机对象以及算法公平性中引入的概念。研究结果依赖于各种领域的概念和技术，包括学习理论、复杂性理论、密码学和博弈论。[机器翻译+人工校对]

This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that focused on the implementation of huge objects that are indistinguishable from the uniform distribution, satisfying some global properties (which they coined truthfulness). Indistinguishability from a single object is motivated by the study of generative models in learning theory and regularity lemmas in graph theory. Problems that are well understood in the setting of pseudorandomness present significant challenges and at times are impossible when considering generative models of huge objects. We demonstrate the versatility of this study by providing a learning algorithm for huge indistinguishable objects in several natural settings including: dense functions and graphs with a truthfulness requirement on the number of ones in the function or edges in the graphs, and a version of the weak regularity lemma for sparse graphs that satisfy some global properties. These and other results generalize basic pseudorandom objects as well as notions introduced in algorithmic fairness. The results rely on notions and techniques from a variety of areas including learning theory, complexity theory, cryptography, and game theory.

https://arxiv.org/pdf/2302.12823.pdf

 

内容中包含的图片若涉及版权问题，请及时与我们联系删除