2026-07-23T13:08:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9078 2024-03-06T10:43:18Z ddc:004 open_access

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces Gurjar, Rohit Thierauf, Thomas Vishnoi, Nisheeth K. Derandomization Isolation Lemma Total unimodularity Near-shortest vectors in Lattices Regular matroids We present a geometric approach towards derandomizing the {Isolation Lemma} by Mulmuley, Vazirani, and Vazirani. In particular, our approach produces a quasi-polynomial family of weights, where each weight is an integer and quasi-polynomially bounded, that can isolate a vertex in any 0/1 polytope for which each face lies in an affine space defined by a totally unimodular matrix. This includes the polytopes given by totally unimodular constraints and generalizes the recent derandomization of the Isolation Lemma 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 vectors of length within 3/2 of the shortest vector in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of circuits of size within 3/2 of the shortest circuit in a regular matroid. This is the technical core of the paper and relies on a variant of Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Gurjar and Thomas Thierauf and Nisheeth K. Vishnoi 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.74 urn:nbn:de:0030-drops-90782 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.74 eng https://creativecommons.org/licenses/by/3.0/legalcode