6
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Possibly related to your first question about derandomizing the isolation lemma: eccc.hpi-web.de/report/2011/151 $\endgroup$ – siuman Mar 25 '13 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$ – András Salamon Mar 26 '13 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 Mar 26 '13 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.