论文标题
独特的二分完美匹配的代数表示
Algebraic Representations of Unique Bipartite Perfect Matching
论文作者
论文摘要
我们使用真实的多项式多项式获得了独特的两部分完美匹配函数及其布尔双重匹配功能的完整特征。基于先前的结果，我们表明，令人惊讶的是，双重描述很稀疏，并且具有低$ \ ell_1 $ -norm-仅在$θ（n \ log n）$中的指数，此结果甚至扩展到其他与匹配相关功能的家庭。我们的方法依赖于匹配覆盖的晶格中的莫比乌斯数字，而我们证明的关键要素是莫比乌斯的反转公式。 这些多项式表示产生复杂性理论结果。例如，我们表明，独特的两分匹配对于经典的决策树来说是回避的，即使对于广义查询模型，也几乎回避了。我们还获得了一个紧密的$θ（n \ log n）$绑定在相关的两党通信任务的日志级上。
We obtain complete characterizations of the Unique Bipartite Perfect Matching function, and of its Boolean dual, using multilinear polynomials over the reals. Building on previous results, we show that, surprisingly, the dual description is sparse and has low $\ell_1$-norm -- only exponential in $Θ(n \log n)$, and this result extends even to other families of matching-related functions. Our approach relies on the Möbius numbers in the matching-covered lattice, and a key ingredient in our proof is Möbius' inversion formula. These polynomial representations yield complexity-theoretic results. For instance, we show that unique bipartite matching is evasive for classical decision trees, and nearly evasive even for generalized query models. We also obtain a tight $Θ(n \log n)$ bound on the log-rank of the associated two-party communication task.
