Timeline for Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 14 at 20:23 | vote | accept | deltaepsilonnn | ||
| Apr 14 at 20:22 | comment | added | deltaepsilonnn | @NealYoung Added! | |
| Apr 14 at 20:22 | history | edited | deltaepsilonnn | CC BY-SA 4.0 |
added 57 characters in body
|
| Apr 13 at 21:35 | answer | added | Neal Young | timeline score: 10 | |
| Apr 13 at 16:23 | review | Suggested edits | |||
| Apr 14 at 11:15 | |||||
| Apr 13 at 15:11 | comment | added | Neal Young | To make the post more self-contained, can you give the definition of $H_i = \{ v : v\cdot w_i = 0 \}$? | |
| Apr 13 at 6:20 | history | edited | D.W. | CC BY-SA 4.0 |
Include paper reference in the body of the post. Avoid use of "EDIT"
|
| Apr 13 at 6:07 | comment | added | D.W. | Please don't use "EDIT: more stuff". Instead, revise the question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755 | |
| Apr 13 at 4:43 | history | edited | Tayfun Pay | CC BY-SA 4.0 |
There is no theorem 4(i)... It is 2.4(i)
|
| Apr 12 at 19:59 | history | edited | deltaepsilonnn | CC BY-SA 4.0 |
added 868 characters in body
|
| Apr 11 at 14:07 | comment | added | deltaepsilonnn | @EmilJeřábek That is as far as I got also. If we assume that $| S_i |$ becomes 1 at some point and $H_1 \cap \cdots \cap H_n = \{ 0^n \}$ then $S_i$ must have become singleton for some $i \le n$. I do not think those two events are independent, but it seems sufficient to show that they have a positive correlation. I am just not seeing it for the case when $0^n \notin S$. | |
| Apr 11 at 11:40 | review | Close votes | |||
| Apr 16 at 3:08 | |||||
| Apr 11 at 11:35 | comment | added | Emil Jeřábek | Clearly, $P_n(S)\ge\Pr[\exists i\,|S_i|=1\& H_1\cap\dots\cap H_n=\{0\}]$. But it’s not clear to me why these two events should be independent (if that is intended to be the argument). | |
| Apr 10 at 19:21 | history | edited | deltaepsilonnn | CC BY-SA 4.0 |
deleted 1 character in body
|
| Apr 10 at 19:21 | history | edited | deltaepsilonnn | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Apr 10 at 19:20 | history | edited | deltaepsilonnn | CC BY-SA 4.0 |
added 18 characters in body
|
| Apr 10 at 19:20 | history | edited | deltaepsilonnn | CC BY-SA 4.0 |
deleted 6 characters in body
|
| S Apr 10 at 19:19 | review | First questions | |||
| Apr 11 at 11:20 | |||||
| S Apr 10 at 19:19 | history | asked | deltaepsilonnn | CC BY-SA 4.0 |