Timeline for How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2018 at 22:59 | vote | accept | Sebastian Oberhoff | ||
| Mar 17, 2018 at 22:59 | comment | added | Sebastian Oberhoff | Now I get what you're saying. You're repeating each clause in the Max-XORSAT formula a number of times that's proportional to the probability that Arthur will select it. | |
| Mar 17, 2018 at 22:52 | comment | added | Yuval Filmus | If you use the reduction in my answer, things will work out. | |
| Mar 17, 2018 at 22:51 | comment | added | Sebastian Oberhoff | How am I not using logarithmically many bits? The only part that requires a larger number of random bits is the part where Arthur chooses a uniformly random triplet. There are ${n\choose 3} = O(n^3)$ triplets. Picking a uniformly random one then requires $\log_2(O(n^3)) = O(\log n)$ random bits. | |
| Mar 17, 2018 at 22:32 | comment | added | Yuval Filmus | Your new question assumes an arbitrary probability distribution on the queries (rather than one generated using only logarithmically many random bits). This corresponds to a MAX-XORSAT instance in which the different constraints are weighted by the probability of the corresponding query. If you don't like weights, you can simulate them by repeating constraints in proportion to their weights. | |
| Mar 17, 2018 at 21:58 | comment | added | Sebastian Oberhoff | I've given my question a major rewrite. Hopefully my question is now clearer. | |
| Mar 17, 2018 at 13:04 | comment | added | Yuval Filmus | You can read my answer using a different terminology. I refer to the entire system as a PCP. The proof itself is the truth assignment. | |
| Mar 17, 2018 at 5:40 | comment | added | Sebastian Oberhoff | You seem to be using terminology differently than I'm familiar with. To me a PCP is an element from $\{0,1\}^k$, where $k$ is of polynomial size. It's the probabilistically checkable proof that Merlin provides to Arthur, not a "distribution over quadruples". | |
| Mar 17, 2018 at 5:09 | history | answered | Yuval Filmus | CC BY-SA 3.0 |