Formalizing Randomized Matching Algorithms

Details Formalizing Randomized Matching Algorithms Formalizing Randomized Matching Algorithms

2011-03-27

arxiv.org/abs/1103.5215v5

Computer Science

Logic in Computer Science

11 pages, expanded version of the conference paper with the same title in proceedings of LICS 2011; several typos were fixed

Scientific paper

Using Je\v{r}\'abek '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.

Affiliated with

Also associated with

No associations

Rating

Formalizing Randomized Matching Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Formalizing Randomized Matching Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Formalizing Randomized Matching Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-94836