Timeline for A candidate for one-way functions
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 6 at 1:25 | comment | added | Daniel Weber | @EmilJeřábek The sizes of $Y$ and $X$ being equal doesn't matter, as you can just pad them. However, I haven't thought about the vertices of $X$ being regular, you're right | |
| Sep 5 at 20:26 | comment | added | Emil Jeřábek | Are you suggesting the problem is NP-complete by Shaeffer's theorem? I don't see how that's supposed to work. Letting $\mathrm{MAJ}_5$ denote majority on 5 variables, $\mathrm{CSP(\{MAJ_5,\neg MAJ_5\})}$ is NP-complete all right, but this is a more general problem, where the sizes of $X$ and $Y$ are unrelated, and vertices of $X$ can have arbitrary degree rather than the graph being 5-regular. | |
| Sep 5 at 15:59 | comment | added | Daniel Weber | Then reversing this is NP-complete by the dichotomy theorem, but I don't know about the average case | |
| Sep 5 at 5:48 | comment | added | Arash Ahadi | What about 5-majority in random bipartite 5-regular graphs? | |
| Sep 5 at 2:11 | history | answered | Daniel Weber | CC BY-SA 4.0 |