Timeline for Concentration Bound of $0/1$ permanent
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17, 2017 at 17:55 | comment | added | Pat Devlin | @JairoBochi : Computing the probability that $P=0$ is a long-standing open problem with lots of intermediate progress and literature on the subject. Do a google search for the very related question asking "what's the probability that a random matrix is singular" [the answer there is conjectured to be roughly equal to the probability that two rows or columns are linearly independent]. In fact, it was hard even to show that $P=0$ is unlikely! (See, e.g., terrytao.files.wordpress.com/2008/04/permanent.pdf among many others.) | |
| Feb 17, 2017 at 6:46 | comment | added | Fedor Petrov | for fixed $\pi$, we vary $\sigma$, and $\tau:=\pi^{-1}\sigma$ runs over all permutations | |
| Feb 17, 2017 at 5:39 | comment | added | Turbo | @FedorPetrov how did you go from sum over $\tau$ to sum over $i$? | |
| Feb 16, 2017 at 13:51 | comment | added | Jairo Bochi | Is it possible to explicitly compute the probability of P=0? | |
| Feb 16, 2017 at 13:23 | history | edited | Fedor Petrov | CC BY-SA 3.0 |
added 4 characters in body
|
| Feb 16, 2017 at 12:53 | comment | added | Jairo Bochi | You mean, close to $(\mathbb{E} P)^2$. | |
| Feb 16, 2017 at 12:20 | history | answered | Fedor Petrov | CC BY-SA 3.0 |