论文标题
双方完美匹配的近似程度
The Approximate Degree of Bipartite Perfect Matching
论文作者
论文摘要
布尔函数的近似程度是实际多项式多项式的最小程度，在布尔hyperean hypercube上的$ \ ell_ \ infty $ -norm中近似它。我们表明，两分的完美匹配函数的大致度，这是所有具有完美匹配的两部分图的指示灯，是$ \widetildeθ（n^{3/2}）$。 上界是通过完全表征代表完美匹配函数的布尔偶对偶的唯一多线性多项式来获得的。至关重要的是，我们表明此多项式具有很小的$ \ ell_1 $ -norm-仅在$θ（n \ log n）$中指数。下边界是通过界定完美匹配函数的光谱灵敏度，即在Hunang2019诱导的Huang2020Degree {Aaronson20degree {aaronson20degree}上的光谱半径}。我们表明，完美匹配的光谱灵敏度正好是$θ（n^{3/2}）$。
The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the $\ell_\infty$-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is $\widetildeΘ(n^{3/2})$. The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small $\ell_1$-norm -- only exponential in $Θ(n \log n)$. The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly $Θ(n^{3/2})$.
