<p>I'm wondering what the best method obtained for <a href="http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem">the Valiant-Vazirani theorem</a> is.  We can state the following criteria:</p>

<p>(1) First and foremost, has anyone been able to derandomize it?</p>

<p>(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 <a href="http://people.csail.mit.edu/madhu/ST07/scribe/lect12.pdf">here</a>?</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-03-25T21:36:07.877Z
Possibly related to your first question about derandomizing the isolation lemma: http://eccc.hpi-web.de/report/2011/151/
siuman
CC BY-SA 3.0
2013-03-26T11:59:31.843Z
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
CC BY-SA 3.0
2013-03-26T15:15:45.047Z
@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
<cc.complexity-theory><sat><lower-bounds>
The latest concerning Valiant-Vazirani
Matt Groff
# The latest concerning Valiant-Vazirani

(Asked by: username_0 on 2013-03-25)

I'm wondering what the best method obtained for [the Valiant-Vazirani theorem](http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_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](http://people.csail.mit.edu/madhu/ST07/scribe/lect12.pdf)?

(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.

**Tags:** cc.complexity-theory, sat, lower-bounds

> **Comments:**
> **username_1**: Possibly related to your first question about derandomizing the isolation lemma: http://eccc.hpi-web.de/report/2011/151/  
> **username_2**: Have you looked at http://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani ?  From the way you phrase this question, it appears not.  
> **username_0**: @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.  

---

## 0 answers

