I'm wondering what the best method obtained for the Valiant-Vazirani theorem is. We can state the following criteria:

(1) First and foremost, has anyone been able to derandomize it?

(2) If not, what is the best running time for converting a SAT instances? And how does this method work? Can we somehow do better than the technique mentioned here?

(3) Out of curiosity, I'd also like to know the size bounds of the converted SAT formula.

The reason I ask is that I'm studying an algorithm that makes use of this, so I'd like to have the best technique available.

  • 6
    $\begingroup$ Possibly related to your first question about derandomizing the isolation lemma: eccc.hpi-web.de/report/2011/151 $\endgroup$
    – siuman
    Commented Mar 25, 2013 at 21:36
  • 3
    $\begingroup$ Have you looked at cstheory.stackexchange.com/questions/7552/… ? From the way you phrase this question, it appears not. $\endgroup$ Commented Mar 26, 2013 at 11:59
  • $\begingroup$ @AndrásSalamon: I have seen it, but I haven't had time to explore it. I'm still interested in the fastest conversion from SAT to UNIQUE-SAT. $\endgroup$
    – Matt Groff
    Commented Mar 26, 2013 at 15:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.