Inverse Problems in Approximate Uniform Generation
Inverse Problems in Approximate Uniform Generation
复制标题
近似一致生成中的反问题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
Anindya De;Ilias Diakonikolas;R. Servedio
我们在近似统一的生成中启动了emph {逆}问题的研究，重点是统一生成各种布尔函数的令人满意的分配。在这样的反问题中，该算法被赋予统一的随机满足不明函数$ f $属于布尔函数的$ c $的未知函数$ f $，目标是输出概率分布$ d $，即$ epsilon $ - - 在总变化距离上关闭到$ f^{ - 1}（1）$的均匀分布。
积极的结果：我们证明了一般的积极结果，为$ c $ c $的有效反向近似均匀产生建立了足够的条件。我们为$ c $定义了一种称为emph {densifier}的新型算法，并显示（粗略地说）如何组合（i）一个密码，（ii）近似计数 /统一的生成算法和（iii）统计查询学习算法，以获得一种近似均匀的生成算法。我们将此一般结果应用于获得半空间等级的poly $（n，1/eps）$ - 时间算法；以及$（poly（n）$ - 大小dnf公式的类别算法的Quasipoly $（N，1/EPS）$ - 时间算法。
负面结果：我们证明了一般的负面结果，表明加密术中某些类型的签名方案的存在意味着某些反近似均匀产生问题的硬度。这意味着没有3-CNF公式的{subpentential} - 时间逆近似均匀生成算法；对于两个半空间的交集；对于2度多项式阈值函数；以及单调2-CNF公式。
最后，我们表明，“正向”近似统一生成问题的复杂性与类$ c $的逆问题的复杂性之间没有一般关系 - 一个可能一个简单难的。
We initiate the study of emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $C$ of Boolean functions, and the goal is to output a probability distribution $D$ which is $epsilon$-close, in total variation distance, to the uniform distribution over $f^{-1}(1)$.
Positive results: We prove a general positive result establishing sufficient conditions for efficient inverse approximate uniform generation for a class $C$. We define a new type of algorithm called a emph{densifier} for $C$, and show (roughly speaking) how to combine (i) a densifier, (ii) an approximate counting / uniform generation algorithm, and (iii) a Statistical Query learning algorithm, to obtain an inverse approximate uniform generation algorithm. We apply this general result to obtain a poly$(n,1/eps)$-time algorithm for the class of halfspaces; and a quasipoly$(n,1/eps)$-time algorithm for the class of $poly(n)$-size DNF formulas.
Negative results: We prove a general negative result establishing that the existence of certain types of signature schemes in cryptography implies the hardness of certain inverse approximate uniform generation problems. This implies that there are no {subexponential}-time inverse approximate uniform generation algorithms for 3-CNF formulas; for intersections of two halfspaces; for degree-2 polynomial threshold functions; and for monotone 2-CNF formulas.
Finally, we show that there is no general relationship between the complexity of the "forward" approximate uniform generation problem and the complexity of the inverse problem for a class $C$ -- it is possible for either one to be easy while the other is hard.