Dai Tri Man Le ; Stephen A. Cook - Formalizing Randomized Matching Algorithms

lmcs:973 - Logical Methods in Computer Science, August 10, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:5)2012
Formalizing Randomized Matching Algorithms

Authors: Dai Tri Man Le ; Stephen A. Cook

    Using Je\v{r}ábek 's framework for probabilistic reasoning, we formalize the correctness of two fundamental RNC^2 algorithms for bipartite perfect matching within the theory VPV for polytime reasoning. The first algorithm is for testing if a bipartite graph has a perfect matching, and is based on the Schwartz-Zippel Lemma for polynomial identity testing applied to the Edmonds polynomial of the graph. The second algorithm, due to Mulmuley, Vazirani and Vazirani, is for finding a perfect matching, where the key ingredient of this algorithm is the Isolating Lemma.


    Volume: Volume 8, Issue 3
    Published on: August 10, 2012
    Accepted on: June 25, 2015
    Submitted on: December 21, 2011
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Logic,F.2.2, F.4.1
    Fundings :
      Source : OpenAIRE Research Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 367 times.
    This article's PDF has been downloaded 354 times.