论文标题
容量下限通过生产
Capacity Lower Bounds via Productization
论文作者
论文摘要
我们对真正稳定多项式的容量给出了急剧的下限，仅取决于其梯度的$ x = 1 $的值。这一结果意味着对2000年的亚摩洛德尼茨基 - 威格德森（Linial-Samorodnitsky-Wigderson）证明的类似不平等的急剧改善，这对于对其永久近似算法的分析至关重要。这种不平等在最近关于操作员缩放及其概括和应用程序的工作中发挥了重要作用，实际上，我们使用界限来为真正的稳定多项式构建一种新的缩放算法。 此外，我们对以前的下界有很大的改善，即非均匀的真实稳定多项式的容量，仅取决于其梯度的值为$ x = 1 $。至关重要的是，这种新的结合与多项式的程度无关，并且对变量数量有单一的指数依赖性。与Karlin-Klein-oveis Gharan的奇妙工作中使用的界限相比，它具有改进的度量TSP的近似因素，在这种依赖性是双重指数的情况下。作者认为这种界限是存在的，因此我们的新结合应意味着对公制TSP的近似因子的进一步改进。 我们开发的新技术证明这种结合是生产力，它说，任何真正的稳定多项式都可以通过线性形式的产物在正矫正的任何点上近似。除了本文的结果之外，我们的主要希望是，用Laurent和Schrijver的话说，这种新技术将使我们避免“令人恐惧的技术”，而这些技术通常伴随着组合的下限。
We give a sharp lower bound on the capacity of a real stable polynomial, depending only on the value of its gradient at $x = 1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000, which was crucial to the analysis of their permanent approximation algorithm. Such inequalities have played an important role in the recent work on operator scaling and its generalizations and applications, and in fact we use our bound to construct a new scaling algorithm for real stable polynomials. In addition, we give a strong improvement on previous lower bounds of the capacity of a non-homogeneous real stable polynomial, depending only on the value of its gradient at $x = 1$. Crucially, this new bound is independent of the degree of the polynomial, and has singly exponential dependence on the number of variables. This compares favorably to the bounds used recently in the fantastic work of Karlin-Klein-Oveis Gharan to give an improved approximation factor for metric TSP, where this dependence is doubly exponential. Such bounds were conjectured to exist by the authors, and thus our new bound should imply further improvement to the approximation factor for metric TSP. The new technique we develop to prove this bound is productization, which says that any real stable polynomial can be approximated at any point in the positive orthant by a product of linear forms. Beyond the results of this paper, our main hope is that this new technique will allow us to avoid "frightening technicalities", in the words of Laurent and Schrijver, that often accompany combinatorial lower bounds.
