<p>I'm currently learning about the analysis of boolean functions (mainly based on their Fourier coefficients) by reading this <a href="http://www.contrib.andrew.cmu.edu/~ryanod/">excellent resource</a> 
There, boolean functions are represented as <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=253">linear combinations of parity functions (which form an orthonormal basis)</a>.</p>

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

CC BY-SA 3.0
2016-04-11T19:07:40.627Z
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.
Sasho Nikolov
CC BY-SA 3.0
2016-04-11T22:11:44.123Z
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. :)
Ryan Williams
<boolean-functions><circuits>
Switching between representations of boolean functions between circuits and Fourier expansions
anaboolguest
# Switching between representations of boolean functions between circuits and Fourier expansions

(Asked by: username_0 on 2016-04-11)

I'm currently learning about the analysis of boolean functions (mainly based on their Fourier coefficients) by reading this [excellent resource](http://www.contrib.andrew.cmu.edu/~ryanod/)
There, boolean functions are represented as [linear combinations of parity functions (which form an orthonormal basis)](http://www.contrib.andrew.cmu.edu/~ryanod/?p=253).

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?

**Tags:** boolean-functions, circuits

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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. :)  

---

## 0 answers

