## Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. (arXiv:1708.02222v2 [cs.DS] UPDATED)

We derandomize the famous Isolation Lemma by Mulmuley, Vazirani, and Vazirani for polytopes given by totally unimodular constraints. That is, we construct a weight assignment such that one vertex in such a polytope is isolated, i.e., there is a unique minimum weight vertex. Our weights are quasi-polynomially bounded and can be constructed in quasi-polynomial time. In fact, our isolation technique works even under the weaker assumption that every face of the polytope lies in an affine space defined by a totally unimodular matrix. This generalizes the recent derandomization results for bipartite perfect matching and matroid intersection. We prove our result by associating a lattice to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of near-shortest vectors in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of near-shortest circ查看全文

## Solidot 文章翻译

 你的名字 留空匿名提交 你的Email或网站 用户可以联系你 标题 简单描述 内容 We derandomize the famous Isolation Lemma by Mulmuley, Vazirani, and Vazirani for polytopes given by totally unimodular constraints. That is, we construct a weight assignment such that one vertex in such a polytope is isolated, i.e., there is a unique minimum weight vertex. Our weights are quasi-polynomially bounded and can be constructed in quasi-polynomial time. In fact, our isolation technique works even under the weaker assumption that every face of the polytope lies in an affine space defined by a totally unimodular matrix. This generalizes the recent derandomization results for bipartite perfect matching and matroid intersection. We prove our result by associating a lattice to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of near-shortest vectors in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of near-shortest circ