1
$\begingroup$

The Valiant-Varizani Theorem is given here. I also liked the description/proof given here - it's fairly straightforward.

I've read these works, and I'm still very shaky with constructing new hashed functions. I start with a 3-SAT function as a product of sums. My question is, for this given 3-SAT function, how do I construct a new function given that there are between $2^k$ and $2^{k+1}$ satisfying truth assignments?

I'd like to see this in great detail, because I plan on implementing this in a project that I'm working on.

MY PROGRESS

I'm thinking that I can just create some function with some new variables (I guess $k+2$ variables) that is true for only one value out of all possible truth assignments. Then, I combine this with the exclusive or of the old SAT function's variables, and this will give me a new function that is true roughly more than $1/8$ of the time.

  • 0
    Judging from the last paragraph, I doubt that you understand the proof of Valiant-Vazirani, in particular the use of pairwise independent family of hash functions in the proof.2012-02-16
  • 0
    @Tsuyoshi Ito: That's exactly what I'd like to understand; the underlying ideas behind pairwise independent families of hash functions. I would gladly accept references to this as an answer. It seems like it should be fairly simple to explain, I just feel like I have to figure out how to do it on my own when I read the works on the theorem.2012-02-16
  • 0
    (1) If you do not understand the proof, then do not say “it’s fairly straightforward.” It may seem cool to say that, but it gives a wrong impression that you believe that you have understood the proof. (2) First, forget _Boolean formulas_ (let alone 3CNF formulas) and understand the _algorithm_ which computes h(x) in the lecture note. It is straightforward, but you cannot go forward without understanding that part. After that, convert the algorithm to a 3CNF formula, either by making some observations about the algorithm or by using the reduction in the Cook-Levin theorem.2012-02-16
  • 0
    @ Tsuyoshi Ito: I'm very sorry, I never meant to mislead anyone. Thank you so much for your helpful words, I will try my best to understand the algorithm. I just feel frustrated because it seems like it should be a simple thing!2012-02-16
  • 0
    @TsuyoshiIto: The algorithm in the lecture notes appears to calculate $h(x)=Ax+b$, where $A$ appears to be an $m \times n$ matrix and $b$ is an $m \times 1$ column matrix, with $A$ and $b$ randomly chosen. Is this correct so far? We can then compare the result to a _vector_, for lack of a better term, that is equivalent to all zeros or all ones (if we are working in binary). Is this also correct?2013-06-24

0 Answers 0