Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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.

share|cite|improve this question
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. – Tsuyoshi Ito Feb 16 '12 at 0:13
@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. – Matt Groff Feb 16 '12 at 0:33
(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. – Tsuyoshi Ito Feb 16 '12 at 0:50
@ 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! – Matt Groff Feb 16 '12 at 0:58
@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? – Matt Groff Jun 24 '13 at 19:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.