<p>It seems to me that Theorem 1 in the paper is false for essentially the same reasons as the Peres example showed in the last version.</p>
<p>Theorem 1 seems to say the following, at least in a special case. Let <span class="math-container">$S$</span> be some finite domain and let <span class="math-container">$H\subset S$</span> denote some subset. Let <span class="math-container">$X$</span> be a random <span class="math-container">$n\times n$</span> array with entries in <span class="math-container">$S$</span> with the property that each <span class="math-container">$X_{i,j}$</span> has some fixed marginal distribution <span class="math-container">$\mathcal{D}$</span> on <span class="math-container">$S$</span> such that <span class="math-container">$H$</span> has positive probability, and let <span class="math-container">$\alpha$</span> denote the conditional distribution of <span class="math-container">$X_{i,j}$</span> obtained by conditioning on <span class="math-container">$X_{i,j}\in H$</span> (which is well-defined since <span class="math-container">$H$</span> has positive probability). Moreover, suppose that the entries of the matrix are jointly independent across rows (but the entries within a row need not be independent). An <span class="math-container">$H$</span>-perfect matching of <span class="math-container">$X$</span> (Def. 5) is a bijection <span class="math-container">$\sigma:[n]\to [n]$</span> such that <span class="math-container">$X_{i,\sigma(i)}\in H$</span> for all <span class="math-container">$i\in [n]$</span>. Let <span class="math-container">$M(X)$</span> denote the (random, possibly empty) set of <span class="math-container">$H$</span>-perfect matchings of <span class="math-container">$X$</span>.</p>
<p>Theorem 1 appears to claim that, <em>under just these assumptions</em>, conditioned on <span class="math-container">$X$</span> having a <span class="math-container">$H$</span>-perfect matching, the distribution of <span class="math-container">$(X_{1,\tau(1)},\ldots,X_{n,\tau(n)})$</span> factorizes as a product measure over <span class="math-container">$\alpha$</span>, where <span class="math-container">$\tau$</span> is chosen uniformly at random among all <span class="math-container">$H$</span>-perfect matchings of <span class="math-container">$X$</span>. That is, for any <span class="math-container">$(x_1,\ldots,x_n)\in H^n$</span>,
<span class="math-container">\begin{equation*}
\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=x_i,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\prod_{i=1}^n \alpha(x_i),
\end{equation*}</span>
where <span class="math-container">$\mathsf{U}[M(X)]$</span> is the uniform distribution over <span class="math-container">$H$</span>-perfect matchings in <span class="math-container">$X$</span>.</p>
<p>For a counterexample, just take Peres' example verbatim. Let <span class="math-container">$S=\{1,2,3\}$</span> and <span class="math-container">$H=\{1,2\}$</span>. For each row of <span class="math-container">$X$</span> independently, with probability <span class="math-container">$1/2$</span>, sample the entries of the row i.i.d. uniformly <span class="math-container">$1$</span> or <span class="math-container">$2$</span>, and with probability <span class="math-container">$1/2$</span>, sample the entries of the row i.i.d. uniformly <span class="math-container">$1$</span> or <span class="math-container">$3$</span>. Call the first situation <span class="math-container">$A$</span> and the second situation <span class="math-container">$B$</span>. The marginal law of each <span class="math-container">$X_{i,j}$</span> is clearly <span class="math-container">$1$</span> with probability <span class="math-container">$1/2$</span> and <span class="math-container">$2$</span> or <span class="math-container">$3$</span> with probability <span class="math-container">$1/4$</span> each. The conditional law <span class="math-container">$\alpha$</span> of <span class="math-container">$X_{i,j}$</span> given <span class="math-container">$X_{i,j}\in H$</span> is <span class="math-container">$X_{i,j}=1$</span> with probability <span class="math-container">$2/3$</span> and <span class="math-container">$X_{i,j}=2$</span> with probability <span class="math-container">$1/3$</span>.</p>
<p>Let's compute
<span class="math-container">\begin{equation*}
\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right).
\end{equation*}</span>
Theorem 1 appears to claim that this should be <span class="math-container">$\alpha(2)^n=(1/3)^n$</span>.</p>
<p>It's easy to see that that the probability <span class="math-container">$M(X)\neq \emptyset$</span> is <span class="math-container">$1-o(1)$</span> by comparison with the probability that a random bipartite graph with <span class="math-container">$1/2$</span> edge probability has a perfect matching via the obvious coupling. Now, we have
<span class="math-container">\begin{equation*}
\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via $A$}\bigg\vert M(X)\neq \emptyset\right).
\end{equation*}</span>
This holds simply because if all entries in any perfect matching are <span class="math-container">$2$</span>, all rows must have been sampled according to situation <span class="math-container">$A$</span>. We thus have
<span class="math-container">\begin{equation*}
\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via $A$}\bigg\vert M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\,\land\,M(X)\neq \emptyset\right)\cdot\Pr\left(\text{all rows sampled via $A$}\vert M(X)\neq \emptyset\right).
\end{equation*}</span>
For the second factor, by Bayes' rule, we have
<span class="math-container">\begin{equation*}
\Pr\left(\text{all rows sampled via $A$}\vert M(X)\neq \emptyset\right)= \frac{\Pr\left(\text{all rows sampled via $A$}\right)}{\Pr(M(X)\neq \emptyset)}=\frac{1+o(1)}{2^n},
\end{equation*}</span>
since the event that all rows are sampled via <span class="math-container">$A$</span> implies there exists a <span class="math-container">$H$</span>-perfect matching.
For the first factor, note that
<span class="math-container">\begin{equation*}
\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\,\land\,M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\right),
\end{equation*}</span>
since again, the event that all rows are sampled via <span class="math-container">$A$</span> implies the existence of <span class="math-container">$H$</span>-perfect matchings. In fact, all perfect matchings are valid if <span class="math-container">$A$</span> occurs since necessarily every entry is in <span class="math-container">$H$</span> by construction. But given <span class="math-container">$A$</span> occurs for every row, the joint law of all entries of the matrix is i.i.d. uniform over <span class="math-container">$1$</span> or <span class="math-container">$2$</span>, independent of the choice of uniform random matching. So we have
<span class="math-container">\begin{equation*}
\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\right)=\frac{1}{2^n}.
\end{equation*}</span>
Putting it together, we find that
<span class="math-container">$\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\frac{1+o(1)}{4^n}\ll \frac{1}{3^n}$</span>.</p>

CC BY-SA 4.0
2024-01-01T16:03:25.177Z
Thank you; I shall accept this answer once I’ve read it more closely.
Jiak Kantang
CC BY-SA 4.0
2023-12-31T22:04:52.823Z
2023-12-31T22:04:52.823Z
Jason Gaitonde
<p>In 2020, András Faragó claimed to have proved that NP = RP (<a href="https://cstheory.stackexchange.com/questions/47337/implications-of-proving-np-rp-on-complexity-theory">discussion</a>; <a href="https://arxiv.org/abs/2008.00601v1" rel="noreferrer">v1 of the paper</a>); the paper was later retracted due to a counterexample to theorem 1.</p>
<p>A few days ago, Faragó posted another <a href="https://arxiv.org/abs/2312.11838" rel="noreferrer">claimed proof</a> to the arXiv. Perhaps, given the first attempt, less attention will be paid to this second paper, but I still wonder whether any similar (or dissimilar) problems have been found.</p>

CC BY-SA 4.0
2023-12-29T08:55:51.527Z
Ancient Greeks [had a story](https://en.wikipedia.org/wiki/The_Boy_Who_Cried_Wolf) that is pertinent to this situation.
Andrej Bauer
CC BY-SA 4.0
2023-12-29T13:30:32.670Z
The expression “Note that our sampling algorithm *(if correct)* has extremely surprising consequences” (emphasis mine) is not exactly inviting confidence.
Jean Abou Samra
CC BY-SA 4.0
2023-12-29T18:52:12.147Z
Well, the author made a mistake once. Maybe he is just trying to be modest :)
Bartosz Bednarczyk
CC BY-SA 4.0
2024-02-06T18:58:02.890Z
To anybody wondering why the preprint was not retracted: I wrote to Faragó, but I believe he must have been quite ill by that point, and it seems that he has now, sadly, [died](https://www.gofundme.com/f/in-memory-of-dr-andras-farago).
Jiak Kantang
<cc.complexity-theory><np>
Status of András Faragó’s (second) claimed proof that NP=RP
Jiak Kantang
# Status of András Faragó’s (second) claimed proof that NP=RP

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

In 2020, András Faragó claimed to have proved that NP = RP ([discussion](https://cstheory.stackexchange.com/questions/47337/implications-of-proving-np-rp-on-complexity-theory); [v1 of the paper](https://arxiv.org/abs/2008.00601v1)); the paper was later retracted due to a counterexample to theorem 1.

A few days ago, Faragó posted another [claimed proof](https://arxiv.org/abs/2312.11838) to the arXiv. Perhaps, given the first attempt, less attention will be paid to this second paper, but I still wonder whether any similar (or dissimilar) problems have been found.

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

> **Comments:**
> **username_1**: Ancient Greeks [had a story](https://en.wikipedia.org/wiki/The_Boy_Who_Cried_Wolf) that is pertinent to this situation.  
> **username_2**: The expression “Note that our sampling algorithm *(if correct)* has extremely surprising consequences” (emphasis mine) is not exactly inviting confidence.  
> **username_3**: Well, the author made a mistake once. Maybe he is just trying to be modest :)  
> **username_0**: To anybody wondering why the preprint was not retracted: I wrote to Faragó, but I believe he must have been quite ill by that point, and it seems that he has now, sadly, [died](https://www.gofundme.com/f/in-memory-of-dr-andras-farago).  

---

## 1 answers

### Answer by username_4 on 2023-12-31. Score: 17 | Accepted answer

It seems to me that Theorem 1 in the paper is false for essentially the same reasons as the Peres example showed in the last version.

Theorem 1 seems to say the following, at least in a special case. Let $S$ be some finite domain and let $H\subset S$ denote some subset. Let $X$ be a random $n\times n$ array with entries in $S$ with the property that each $X\_{i,j}$ has some fixed marginal distribution $\mathcal{D}$ on $S$ such that $H$ has positive probability, and let $\alpha$ denote the conditional distribution of $X\_{i,j}$ obtained by conditioning on $X\_{i,j}\in H$ (which is well-defined since $H$ has positive probability). Moreover, suppose that the entries of the matrix are jointly independent across rows (but the entries within a row need not be independent). An $H$-perfect matching of $X$ (Def. 5) is a bijection $\sigma:[n]\to [n]$ such that $X\_{i,\sigma(i)}\in H$ for all $i\in [n]$. Let $M(X)$ denote the (random, possibly empty) set of $H$-perfect matchings of $X$.

Theorem 1 appears to claim that, *under just these assumptions*, conditioned on $X$ having a $H$-perfect matching, the distribution of $(X\_{1,\tau(1)},\ldots,X\_{n,\tau(n)})$ factorizes as a product measure over $\alpha$, where $\tau$ is chosen uniformly at random among all $H$-perfect matchings of $X$. That is, for any $(x\_1,\ldots,x\_n)\in H^n$,
\begin{equation\*}
\Pr\_{\tau\sim \mathsf{U}[M(X)]}\left(X\_{i,\tau(i)}=x\_i,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\prod\_{i=1}^n \alpha(x\_i),
\end{equation\*}
where $\mathsf{U}[M(X)]$ is the uniform distribution over $H$-perfect matchings in $X$.

For a counterexample, just take Peres' example verbatim. Let $S=\{1,2,3\}$ and $H=\{1,2\}$. For each row of $X$ independently, with probability $1/2$, sample the entries of the row i.i.d. uniformly $1$ or $2$, and with probability $1/2$, sample the entries of the row i.i.d. uniformly $1$ or $3$. Call the first situation $A$ and the second situation $B$. The marginal law of each $X\_{i,j}$ is clearly $1$ with probability $1/2$ and $2$ or $3$ with probability $1/4$ each. The conditional law $\alpha$ of $X\_{i,j}$ given $X\_{i,j}\in H$ is $X\_{i,j}=1$ with probability $2/3$ and $X\_{i,j}=2$ with probability $1/3$.

Let's compute
\begin{equation\*}
\Pr\_{\tau\sim \mathsf{U}[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right).
\end{equation\*}
Theorem 1 appears to claim that this should be $\alpha(2)^n=(1/3)^n$.

It's easy to see that that the probability $M(X)\neq \emptyset$ is $1-o(1)$ by comparison with the probability that a random bipartite graph with $1/2$ edge probability has a perfect matching via the obvious coupling. Now, we have
\begin{equation\*}
\Pr\_{\tau\sim \mathsf{U}[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\Pr\_{\tau\sim U[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via $A$}\bigg\vert M(X)\neq \emptyset\right).
\end{equation\*}
This holds simply because if all entries in any perfect matching are $2$, all rows must have been sampled according to situation $A$. We thus have
\begin{equation\*}
\Pr\_{\tau\sim \mathsf{U}[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via $A$}\bigg\vert M(X)\neq \emptyset\right)=\Pr\_{\tau\sim U[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\,\land\,M(X)\neq \emptyset\right)\cdot\Pr\left(\text{all rows sampled via $A$}\vert M(X)\neq \emptyset\right).
\end{equation\*}
For the second factor, by Bayes' rule, we have
\begin{equation\*}
\Pr\left(\text{all rows sampled via $A$}\vert M(X)\neq \emptyset\right)= \frac{\Pr\left(\text{all rows sampled via $A$}\right)}{\Pr(M(X)\neq \emptyset)}=\frac{1+o(1)}{2^n},
\end{equation\*}
since the event that all rows are sampled via $A$ implies there exists a $H$-perfect matching.
For the first factor, note that
\begin{equation\*}
\Pr\_{\tau\sim U[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\,\land\,M(X)\neq \emptyset\right)=\Pr\_{\tau\sim U[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\right),
\end{equation\*}
since again, the event that all rows are sampled via $A$ implies the existence of $H$-perfect matchings. In fact, all perfect matchings are valid if $A$ occurs since necessarily every entry is in $H$ by construction. But given $A$ occurs for every row, the joint law of all entries of the matrix is i.i.d. uniform over $1$ or $2$, independent of the choice of uniform random matching. So we have
\begin{equation\*}
\Pr\_{\tau\sim U[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\right)=\frac{1}{2^n}.
\end{equation\*}
Putting it together, we find that
$\Pr\_{\tau\sim \mathsf{U}[M(X)]}\left(X\_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\frac{1+o(1)}{4^n}\ll \frac{1}{3^n}$.

> **Comments:**
> **username_0**: Thank you; I shall accept this answer once I’ve read it more closely.  

---

