<p>Suppose we have two bipartite graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with perfect matching count <span class="math-container">$P_1$</span> and <span class="math-container">$P_2$</span> respectively then their disjoint union gives a bipartite graph with perfect matching <span class="math-container">$P_1P_2$</span>.</p>
<blockquote>
<p>Is there a graph construction in polynomial time to get a bipartite graph from  <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with perfect matching count mod <span class="math-container">$2^i$</span> exactly <span class="math-container">$(P_1+P_2)\bmod2^i$</span> where <span class="math-container">$i=\Omega(n)$</span> is allowed?</p>
</blockquote>
<p>Related: <a href="https://cstheory.stackexchange.com/questions/38772/is-permanent-reducible">Is Permanent $+$-reducible?</a></p>

CC BY-SA 4.0
2024-04-04T15:39:53.207Z
Doesn't my answer to that other question already answer this question?
Joshua Grochow
CC BY-SA 4.0
2024-04-04T16:12:04.907Z
I thought your answer had bipartite graph with weights. This one seems like a relaxed version where we only require modulus to agree.
Turbo
CC BY-SA 4.0
2024-04-04T18:31:34.153Z
You don’t need weights if you work modulo $p$ (for $p$ odd). You can take all weights to be in $\{0,\dots,p-1\}$, and then reduce them easily to $\{0,1\}$ as in the proof of Valiant’s theorem. Thus, the other answer does answer this question.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T19:48:12.193Z
Unfortunately as you know, the construction fails for char $2$ case.
Turbo
CC BY-SA 4.0
2024-04-04T20:04:23.433Z
For $p=2$, the problem is trivial as it is just determinant. Just compute the result and pick one of two fixed graphs.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T20:07:20.443Z
Ah I see.. corrected the confusion.
Turbo
CC BY-SA 4.0
2024-04-04T20:29:50.383Z
You didn't correct any of your confusion. You are given the graph, hence you know what $P_i\bmod2$ is. You can't prevent a polytime algorithm from computing it. There is no coherent way how to tell that an algorithm computes some particular value as part of its inner workings, just obfuscate it enough.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T20:33:32.657Z
In any case, for $p=2$, you can construct a suitable graph even by a DLOGTIME function using the $\oplus L$-completeness of determinant mod 2, just like the original answer used the $\#P$-completeness of permanent.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T20:36:49.777Z
@Emil: but you can ask for a function that satisfies some natural properties, such as having infinite image, being injective, preserving various graph properties, being associative, etc. Asking for the reduction to be AC0 rules out computing det first.
Joshua Grochow
CC BY-SA 4.0
2024-04-04T20:46:50.683Z
My interest is also for $\bmod p^i$ case where $i\geq1$ and $i=\Omega(n)$ specifically.
Turbo
CC BY-SA 4.0
2024-04-04T20:52:22.280Z
@JoshuaGrochow Perhaps. But then the question has to include the desired natural properties, not empty meaningless statements such as “without knowing $P_1\bmod p$”.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T21:19:45.033Z
The original construction works modulo any odd $M$ given in binary. (You can also combine graphs that work modulo coprime $M_0$ and $M_1$ to a graph that works modulo $M_0M_1$ using CRT.) Thus, the only remaining question is if there is something that works modulo large powers of $2$.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T22:02:50.617Z
@EmilJeřábek: Fair. (Another thought: it seems reasonable to ask for it to be a p-projection, and that would also rule out first computing the determinant. But it depends on what the OP is looking for.)
Joshua Grochow
CC BY-SA 4.0
2024-04-04T22:48:05.687Z
Ok I have corrected to the problem I am interested in.
Turbo
CC BY-SA 4.0
2024-04-04T22:50:40.267Z
@JoshuaGrochow does $qp$-projection exist when $i=O(\log^j n)$ at any fixed $j$?
Turbo
<cc.complexity-theory><permanent>
On mod $2^i$ $+$-reducibility of permanent
Turbo
# On mod $2^i$ $+$-reducibility of permanent

(Asked by: username_0 on 2023-12-25)

Suppose we have two bipartite graphs $G\_1$ and $G\_2$ with perfect matching count $P\_1$ and $P\_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P\_1P\_2$.

> Is there a graph construction in polynomial time to get a bipartite graph from $G\_1$ and $G\_2$ with perfect matching count mod $2^i$ exactly $(P\_1+P\_2)\bmod2^i$ where $i=\Omega(n)$ is allowed?

Related: [Is Permanent $+$-reducible?](https://cstheory.stackexchange.com/questions/38772/is-permanent-reducible)

**Tags:** cc.complexity-theory, permanent

> **Comments:**
> **username_1**: Doesn't my answer to that other question already answer this question?  
> **username_0**: I thought your answer had bipartite graph with weights. This one seems like a relaxed version where we only require modulus to agree.  
> **username_2**: You don’t need weights if you work modulo $p$ (for $p$ odd). You can take all weights to be in $\{0,\dots,p-1\}$, and then reduce them easily to $\{0,1\}$ as in the proof of Valiant’s theorem. Thus, the other answer does answer this question.  
> **username_0**: Unfortunately as you know, the construction fails for char $2$ case.  
> **username_2**: For $p=2$, the problem is trivial as it is just determinant. Just compute the result and pick one of two fixed graphs.  
> **username_0**: Ah I see.. corrected the confusion.  
> **username_2**: You didn't correct any of your confusion. You are given the graph, hence you know what $P_i\bmod2$ is. You can't prevent a polytime algorithm from computing it. There is no coherent way how to tell that an algorithm computes some particular value as part of its inner workings, just obfuscate it enough.  
> **username_2**: In any case, for $p=2$, you can construct a suitable graph even by a DLOGTIME function using the $\oplus L$-completeness of determinant mod 2, just like the original answer used the $\#P$-completeness of permanent.  
> **username_1**: @Emil: but you can ask for a function that satisfies some natural properties, such as having infinite image, being injective, preserving various graph properties, being associative, etc. Asking for the reduction to be AC0 rules out computing det first.  
> **username_0**: My interest is also for $\bmod p^i$ case where $i\geq1$ and $i=\Omega(n)$ specifically.  
> **username_2**: @JoshuaGrochow Perhaps. But then the question has to include the desired natural properties, not empty meaningless statements such as “without knowing $P_1\bmod p$”.  
> **username_2**: The original construction works modulo any odd $M$ given in binary. (You can also combine graphs that work modulo coprime $M_0$ and $M_1$ to a graph that works modulo $M_0M_1$ using CRT.) Thus, the only remaining question is if there is something that works modulo large powers of $2$.  
> **username_1**: @EmilJeřábek: Fair. (Another thought: it seems reasonable to ask for it to be a p-projection, and that would also rule out first computing the determinant. But it depends on what the OP is looking for.)  
> **username_0**: Ok I have corrected to the problem I am interested in.  
> **username_0**: @JoshuaGrochow does $qp$-projection exist when $i=O(\log^j n)$ at any fixed $j$?  

---

## 0 answers

