Minimum Circuit Size, Graph Isomorphism, and Related Problems
Minimum Circuit Size, Graph Isomorphism, and Related Problems
复制标题
最小电路尺寸、图同构及相关问题
DOI：
10.1137/17m1157970
复制
发表时间：
2018
影响因子：
1.6
通讯作者：
Morgan, Andrew
中科院分区：
文献类型：
--
作者：
Allender, Eric;Grochow, Joshua A.;van Melkebeek, Dieter;Moore, Cristopher;Morgan, Andrew
我们研究了判断给定真值表是否可以用给定大小的电路(最小电路大小问题，简称MCSP)来描述以及表示为MKTP的变体的计算能力，其中电路大小被多项式相关的Kolmogorov测度所代替。在我们的工作之前，从所谓的棘手问题到MCSP/MKTP的所有简化都取决于MCSP/MKTP区分随机分布和基于硬度的伪随机生成器构造产生的分布的能力。受著名的交互式证明系统的启发，我们开发了一种完全不同的方法来证明图同构的补集。它产生了从GI到MKTP的具有零侧误差的随机归约。我们推广了这一结果，并证明了GI可以被任何基础群满足某些基本性质的同构问题所代替。实例化包括线性码等价、置换群共轭和矩阵子空间共轭。在此过程中，我们开发了可有效解码的同构类编码，并实现了达到或接近信息论最优的压缩；这些编码可能是独立感兴趣的。
We study the computational power of deciding whether a given truth table can be described by a circuit of a given size (the minimum circuit size problem, or MCSP for short) and of the variant denoted as MKTP, where circuit size is replaced by a polynomially related Kolmogorov measure. Prior to our work, all reductions from supposedly intractable problems to MCSP/MKTP hinged on the power of MCSP/MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of graph isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include linear code equivalence, permutation group conjugacy, and matrix subspace conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
登录
查看更多内容
来自自然下界的算法
DOI：
--
发表时间：
2016
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
M. Carmosino;R. Impagliazzo;Valentine Kabanets;A. Kolokolova
通讯作者：
A. Kolokolova
DOI：
10.1109/sfcs.2002.1181999
发表时间：
2002-11
期刊：
The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
影响因子：
--
作者：
V. Arvind;Piyush P. Kurur
通讯作者：
V. Arvind;Piyush P. Kurur
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
W. Kantor;Kay Magaard
通讯作者：
Kay Magaard
计算复杂性理论中资源有限的柯尔莫哥洛夫复杂性的普遍影响
DOI：
10.1016/j.jcss.2010.06.004
发表时间：
2009
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Eric Allender;M. Koucký;Detlef Ronneburger;Sambuddha Roy
通讯作者：
Sambuddha Roy
零知识和电路最小化
DOI：
10.1016/j.ic.2017.04.004
发表时间：
2014
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Eric Allender;Bireswar Das
通讯作者：
Bireswar Das