Bounds on the Norms of Uniform Low Degree Graph Matrices
Bounds on the Norms of Uniform Low Degree Graph Matrices
复制标题
均匀低次图矩阵范数的界
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Aaron Potechin
中科院分区：
文献类型：
--
作者：
Dhruv Medarametla;Aaron Potechin
平方和层次结构是我们所知道的解决组合优化问题的最强大的工具之一。然而，它的性能仅被部分理解。提高我们对平方和层次的理解是计算复杂性理论中的一个主要开放问题。
分析平方和层次结构的一个关键组成部分是理解某些矩阵的行为，这些矩阵的元素是随机的，但不是独立的。对于这些矩阵，存在随机输入图，并且矩阵的每个条目是该输入图的边的低次函数。此外，当我们置换输入图的顶点时，这些矩阵通常是不变的（作为输入图的函数）。在本文中，我们将所有这类矩阵的范数约束到一个多对数因子。
The Sum Of Squares hierarchy is one of the most powerful tools we know of for solving combinatorial optimization problems. However, its performance is only partially understood. Improving our understanding of the sum of squares hierarchy is a major open problem in computational complexity theory.
A key component of analyzing the sum of squares hierarchy is understanding the behavior of certain matrices whose entries are random but not independent. For these matrices, there is a random input graph and each entry of the matrix is a low degree function of the edges of this input graph. Moreoever, these matrices are generally invarint (as a function of the input graph) when we permute the vertices of the input graph. In this paper, we bound the norms of all such matrices up to a polylogarithmic factor.