<p>Getting Least Significant Bit of $0/1$ permanent is in $P$. </p>

<p>Since Permanent has constant factor approximation algorithm we can get Most Significant Bit of $0/1$ permanent in $BPP$.</p>

<ol>
<li><p>Then for what ranges of bits of $0/1$ permanent is computing any of them hard?</p></li>
<li><p>In particular is there any significance to the middle bit?</p></li>
</ol>

CC BY-SA 3.0
2017-07-15T09:27:16.267Z
If you can get the most significant bit (which is essentially PP), then that implies PH is in P by Toda's theorem. I think this also answers your second question since the middle bit is the hardest. Can you point to a reference for the constant factor approximation algorithm for the permanent?
Nikhil
CC BY-SA 3.0
2017-07-15T09:30:34.853Z
@Nikhil $0/1$ permanent can be approximated to $(1+\epsilon)$ ratio by JSV algorithm right?
Turbo
CC BY-SA 3.0
2017-07-15T23:45:15.827Z
@Gamow $\mbox{negative numbers}<0<1$ :).
Turbo
CC BY-SA 3.0
2017-07-16T19:07:57.730Z
There is a related paper.
Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán: The Power of the Middle Bit of a #P Function. J. Comput. Syst. Sci. 50(3): 456-467 (1995).

Every problem in the polynomial hierachy can be reduced to the middle bit of a suitable #P-function. By standard parsimoneous reductions to the permanent this should give some answer to question 2 (but I have not thought through all details).
Thomas S
CC BY-SA 3.0
2017-07-23T19:01:47.740Z
@ThomasS: Parsimonious reductions to 0/1-perm imply P=NP (b/c deciding the existence of perfect matchings is easy). [Valiant's](https://doi.org/10.1016/0304-3975(79)90044-6) reduction to 0/1-perm uses CRT, so the middle bits may combine in complicated ways. [Aaronson](https://doi.org/10.1098/rspa.2011.0232) gave another proof for #P-hardness of perm, but to reduce to 0/1-perm uses the same lemmas as Valiant. It may not be easy to get around this (see, e.g., [here](https://arxiv.org/abs/1510.08417)). GKRST mention that the mid-bit of #SAT can be used, which does have parsimonious reductions.
Joshua Grochow
CC BY-SA 3.0
2017-07-23T19:03:12.097Z
The GKRST paper mentioned by Thomas S gives more parts of the answer to (1): e.g. they point out that the first and last $O(\log n)$ bits are easy.
Joshua Grochow
CC BY-SA 3.0
2017-07-23T21:16:52.503Z
@JoshuaGrochow you are right. My comment was a bit sloppy. The reductions are not parsimonious. However, they can be chosen such that the function value (as a bit string) occurs as a substring of the value of the permanent (as a bitstring) and by suitable shifting the middle bit of the value of the #P-function can become the middle bit of the value of the respective permanent.
Thomas S
CC BY-SA 3.0
2017-07-23T21:57:58.563Z
@ThomasS: How? I don't see how to do this. Valiant's reduction to integer perm has the property you state, but crucially uses negative numbers. When you use CRT to reduce to 0/1 perm I don't see how to easily control which bits appear where.
Joshua Grochow
CC BY-SA 3.0
2017-07-24T05:03:12.187Z
@JoshuaGrochow There is a further reduction to 0-1-Permanent, see, e.g. Papadimitriou's book. Or Arora,Barak. They do it modulo 2^N+1, for some polynomial N, but it works equally well modulo 2^N. This gives you some additional bits on the left of the bit string, but that's fine, in our context.
Thomas S
CC BY-SA 3.0
2017-07-24T14:23:47.390Z
@ThomasS: Ah, excellent! Somehow I hadn't seen this reduction before nor thought of it, though in retrospect it is very clear.
Joshua Grochow
CC BY-SA 3.0
2017-07-27T09:00:58.347Z
@Turbo Your claim about the most significant bit of the permanent being computable in BPP is not quite true (it would imply a collapse of PH otherwise). I think the problem is that you are inferring being approximable up to a constant factor to imply the most significant bits being correctly computed. This is not true (approximation errors could cause carries etc).
Nikhil
CC BY-SA 3.0
2017-07-27T09:05:10.510Z
@Nikhil why would PH collapse?
Turbo
<permanent>
What ranges of bits of $0/1$ permanent are hard to compute?
Turbo
# What ranges of bits of $0/1$ permanent are hard to compute?

(Asked by: username_0 on 2017-07-14)

Getting Least Significant Bit of $0/1$ permanent is in $P$.

Since Permanent has constant factor approximation algorithm we can get Most Significant Bit of $0/1$ permanent in $BPP$.

1. Then for what ranges of bits of $0/1$ permanent is computing any of them hard?
2. In particular is there any significance to the middle bit?

**Tags:** permanent
> **Comments:**
> **username_1**: If you can get the most significant bit (which is essentially PP), then that implies PH is in P by Toda's theorem. I think this also answers your second question since the middle bit is the hardest. Can you point to a reference for the constant factor approximation algorithm for the permanent?  
> **username_0**: @Nikhil $0/1$ permanent can be approximated to $(1+\epsilon)$ ratio by JSV algorithm right?  
> **username_0**: @Gamow $\mbox{negative numbers}<0<1$ :).  
> **username_2**: There is a related paper. Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán: The Power of the Middle Bit of a #P Function. J. Comput. Syst. Sci. 50(3): 456-467 (1995).  Every problem in the polynomial hierachy can be reduced to the middle bit of a suitable #P-function. By standard parsimoneous reductions to the permanent this should give some answer to question 2 (but I have not thought through all details).  
> **username_3**: @ThomasS: Parsimonious reductions to 0/1-perm imply P=NP (b/c deciding the existence of perfect matchings is easy). [Valiant's](https://doi.org/10.1016/0304-3975(79)90044-6) reduction to 0/1-perm uses CRT, so the middle bits may combine in complicated ways. [Aaronson](https://doi.org/10.1098/rspa.2011.0232) gave another proof for #P-hardness of perm, but to reduce to 0/1-perm uses the same lemmas as Valiant. It may not be easy to get around this (see, e.g., [here](https://arxiv.org/abs/1510.08417)). GKRST mention that the mid-bit of #SAT can be used, which does have parsimonious reductions.  
> **username_3**: The GKRST paper mentioned by Thomas S gives more parts of the answer to (1): e.g. they point out that the first and last $O(\log n)$ bits are easy.  
> **username_2**: @JoshuaGrochow you are right. My comment was a bit sloppy. The reductions are not parsimonious. However, they can be chosen such that the function value (as a bit string) occurs as a substring of the value of the permanent (as a bitstring) and by suitable shifting the middle bit of the value of the #P-function can become the middle bit of the value of the respective permanent.  
> **username_3**: @ThomasS: How? I don't see how to do this. Valiant's reduction to integer perm has the property you state, but crucially uses negative numbers. When you use CRT to reduce to 0/1 perm I don't see how to easily control which bits appear where.  
> **username_2**: @JoshuaGrochow There is a further reduction to 0-1-Permanent, see, e.g. Papadimitriou's book. Or Arora,Barak. They do it modulo 2^N+1, for some polynomial N, but it works equally well modulo 2^N. This gives you some additional bits on the left of the bit string, but that's fine, in our context.  
> **username_3**: @ThomasS: Ah, excellent! Somehow I hadn't seen this reduction before nor thought of it, though in retrospect it is very clear.  
> **username_1**: @Turbo Your claim about the most significant bit of the permanent being computable in BPP is not quite true (it would imply a collapse of PH otherwise). I think the problem is that you are inferring being approximable up to a constant factor to imply the most significant bits being correctly computed. This is not true (approximation errors could cause carries etc).  
> **username_0**: @Nikhil why would PH collapse?  

---

## 0 answers

