• DocumentCode
    3642823
  • Title

    Formalizing Randomized Matching Algorithms

  • Author

    Dai Tri Man Lê;Stephen A. Cook

  • Author_Institution
    Dept. of Comput. Sci., Univ. of Toronto, Toronto, ON, Canada
  • fYear
    2011
  • fDate
    6/1/2011 12:00:00 AM
  • Firstpage
    185
  • Lastpage
    194
  • Abstract
    Using Jerábek´s framework for probabilistic reasoning, we formalize the correctness of two fundamental RNC2 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.
  • Keywords
    "Polynomials","Cognition","Bipartite graph","Complexity theory","Probabilistic logic","Vocabulary","Testing"
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science (LICS), 2011 26th Annual IEEE Symposium on
  • ISSN
    1043-6871
  • Print_ISBN
    978-1-4577-0451-2
  • Type

    conf

  • DOI
    10.1109/LICS.2011.12
  • Filename
    5970216
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3642823