论文标题
观察对称电路
Observations on Symmetric Circuits
论文作者
论文摘要
我们研究对称算术电路，并在Dawar和Wilsenach（Arxiv 2020）给出的下限上有所改善。他们的结果显示由对称电路计算的永久性的指数下限。我们扩展了此结果，以显示永久下限的更简单的证明，并表明大量多项式在此模型中具有指数下限。实际上，我们证明所有包含至少一个永久性单元的多项式在对称计算模型中都具有指数大小的下限。我们还显示了较小群体的超值下限。我们支持我们的结论，即通过表明在选择多项式的随机过程中，该组比多项式重要得多，不遇到超级多项式下限的概率呈指数较低。
We study symmetric arithmetic circuits and improve on lower bounds given by Dawar and Wilsenach (ArXiv 2020). Their result showed an exponential lower bound of the permanent computed by symmetric circuits. We extend this result to show a simpler proof of the permanent lower bound and show that a large class of polynomials have exponential lower bounds in this model. In fact, we prove that all polynomials that contain at least one monomial of the permanent have exponential size lower bounds in the symmetric computation model. We also show super-polynomial lower bounds for smaller groups. We support our conclusion that the group is much more important than the polynomial by showing that on a random process of choosing polynomials, the probability of not encountering a super-polynomial lower bound is exponentially low.
