Skip to main content
Theoretical Computer Science

Return to Answer

Bounty Ended with 200 reputation awarded by Gil Kalai
deleted 4 characters in body
Source Link
Luca Trevisan
Luca Trevisan
  • 5k
  • 29
  • 34

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \otimes \cdots \otimes x_i$$f(x,i):= x_1 \oplus \cdots \oplus x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \otimes \cdots \otimes x_i$$x_1 \oplus \cdots \oplus x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \otimes \cdots \otimes x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \otimes \cdots \otimes x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \oplus \cdots \oplus x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \oplus \cdots \oplus x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

latex fun
Source Link
Suresh Venkat
Suresh Venkat
  • 32.2k
  • 4
  • 97
  • 272

Gil, would something like this be a counterexample?

Let m$m$ be such that n=m+log m$n=m+\log m$, and think of an n$n$-bit input as being a pair $(x,i)$ where x$x$ is an m-bit string (x1,...,xm)$(x_1,\ldots ,x_m)$ and i$i$ is an integer in the range 1,...,m$1,\ldots,m$ written in binary.

Then we define f(x,i):= x1 xor ... xor xi$f(x,i):= x_1 \otimes \cdots \otimes x_i$

Now for each i=1,...,m$i=1,\ldots,m$ the function f() has 1/m$1/m$ correlation with the Fourier character x1 xor... xor xi$x_1 \otimes \cdots \otimes x_i$, and so the "level i" has at least a 1/m^2$1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

Gil, would something like this be a counterexample?

Let m be such that n=m+log m, and think of an n-bit input as being a pair $(x,i)$ where x is an m-bit string (x1,...,xm) and i is an integer in the range 1,...,m written in binary.

Then we define f(x,i):= x1 xor ... xor xi

Now for each i=1,...,m the function f() has 1/m correlation with the Fourier character x1 xor... xor xi, and so the "level i" has at least a 1/m^2 fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \otimes \cdots \otimes x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \otimes \cdots \otimes x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

Source Link
Luca Trevisan
Luca Trevisan
  • 5k
  • 29
  • 34

Gil, would something like this be a counterexample?

Let m be such that n=m+log m, and think of an n-bit input as being a pair $(x,i)$ where x is an m-bit string (x1,...,xm) and i is an integer in the range 1,...,m written in binary.

Then we define f(x,i):= x1 xor ... xor xi

Now for each i=1,...,m the function f() has 1/m correlation with the Fourier character x1 xor... xor xi, and so the "level i" has at least a 1/m^2 fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).