6
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ cf: 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. $\endgroup$ – Clement C. Aug 31 '17 at 12:38
  • $\begingroup$ You can find one extension for depth-2 LTFs in Theorem 2.3 here: arxiv.org/abs/1511.07860 $\endgroup$ – Alex Golovnev Sep 5 '17 at 18:01
  • $\begingroup$ 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. $\endgroup$ – gradstudent Sep 6 '17 at 4:26

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.