I'm currently learning about the analysis of boolean functions (mainly based on their Fourier coefficients) by reading this excellent resource There, boolean functions are represented as linear combinations of parity functions (which form an orthonormal basis).

From other areas I'm used to functions being represented as circuits. My question therefore is: What is the most efficient/simple way to convert a function from its representation by Fourier coefficients to a small circuit and vice versa?

  • 2
    $\begingroup$ You should check Chapter 4 of the O'Donnell's book. Relating the Fourier representation of a function to the structure of a circuit representing it is not easy. There are interesting open questions even about the simplest circuits: DNFs. This is very much an area of current research. $\endgroup$ – Sasho Nikolov Apr 11 '16 at 19:07
  • 2
    $\begingroup$ Given the Fourier expansion of a function you can recover its truth table in $2^n poly(n) $ time, and given the truth table you can get the Fourier expansion in this time. Hence your question is equivalent to computing truth tables of circuits, which is at least as hard as solving SAT in less than $2^n $ time (which in turn is at least as hard as showing NEXP is not in P/poly). So.... hard problem. :) $\endgroup$ – Ryan Williams Apr 11 '16 at 22:11

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.