6

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.

Community
  • 1
Matt Groff
  • 2,100
  • 13
  • 19
  • 6
    Possibly related to your first question about derandomizing the isolation lemma: http://eccc.hpi-web.de/report/2011/151/ – siuman Mar 25 '13 at 21:36
  • 3
    Have you looked at http://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani ? From the way you phrase this question, it appears not. – András Salamon Mar 26 '13 at 11:59
  • @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. – Matt Groff Mar 26 '13 at 15:15

0 Answers0