<p>The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients. </p>

<p>Are there other circuits for which such a Chow's theorem is known to hold? Like for depth $2$ LTFs? Or are there reasons to believe that such extensions can't be true? </p>

CC BY-SA 3.0
2017-08-31T12:38:49.143Z
cf: https://arxiv.org/abs/1206.0985 "A natural generalization of Chows theorem holds in this setting; more precisely, Bruck [Bru90] has shown that the Fourier coefficients of degree at most $d$ uniquely specify any degree-$d$ PTF within the space of all Boolean or even bounded functions."
>${}\\$ [Bru90] J. Bruck. *Harmonic analysis of polynomial threshold functions*. SIAM Journal on Discrete Mathematics, 3(2):168–177, 1990.
Clement C.
CC BY-SA 3.0
2017-09-05T18:01:14.843Z
You can find one extension for depth-2 LTFs in Theorem 2.3 here: https://arxiv.org/abs/1511.07860
Alex Golovnev
CC BY-SA 3.0
2017-09-06T04:26:58.083Z
Why do you think this theorem is an extension of Chow's Theorem? This doesn't seem to say that depth 2 LTFs are uniquely determined by some non-trivial subset of its Fourier coefficients.
gradstudent
<circuit-complexity><boolean-functions><fourier-analysis>
Are there generalizations for Chow's theorem?
gradstudent
# Are there generalizations for Chow's theorem?

(Asked by: username_0 on 2017-08-31)

The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients.

Are there other circuits for which such a Chow's theorem is known to hold? Like for depth $2$ LTFs? Or are there reasons to believe that such extensions can't be true?

**Tags:** circuit-complexity, boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: cf: https://arxiv.org/abs/1206.0985 "A natural generalization of Chows theorem holds in this setting; more precisely, Bruck [Bru90] has shown that the Fourier coefficients of degree at most $d$ uniquely specify any degree-$d$ PTF within the space of all Boolean or even bounded functions." >${}\\$ [Bru90] J. Bruck. *Harmonic analysis of polynomial threshold functions*. SIAM Journal on Discrete Mathematics, 3(2):168–177, 1990.  
> **username_2**: You can find one extension for depth-2 LTFs in Theorem 2.3 here: https://arxiv.org/abs/1511.07860  
> **username_0**: Why do you think this theorem is an extension of Chow's Theorem? This doesn't seem to say that depth 2 LTFs are uniquely determined by some non-trivial subset of its Fourier coefficients.  

---

## 0 answers

