Applications of Schwartz-Zippel test whether a graph has perfect matching; test isomorphism of rooted trees; distance property of Reed-Muller codes; proof of hardness vs randomness tradeoff; ● algebraic construction of probabilistically checkable proofs(PCP);
Applications of Schwartz-Zippel • test whether a graph has perfect matching; • test isomorphism of rooted trees; • distance property of Reed-Muller codes; • proof of hardness vs randomness tradeoff; • algebraic construction of probabilistically checkable proofs (PCP); •
Bipartite Perfect Matching bipartite graph perfect matchings 三凶 G([n],[n],E determine whether a bipartite graph has PM: Hall's theorem:enumerates all subset of [n] Hungarian method:O(n3) Hopcroft-Karp algorithm:O(mVn) ● efficient parallel algorithms?
Bipartite Perfect Matching 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand bipartite graph G([n],[n],E) perfect matchings • Hall’s theorem: enumerates all subset of [n] • Hungarian method: O(n3) • Hopcroft-Karp algorithm: O(m√n) • efficient parallel algorithms? determine whether a bipartite graph has PM: