Paper Info

Title | ||
---|---|---|

Polynomial threshold functions, AC0 functions, and spectral norms |

Abstract | ||
---|---|---|

The class of polynomial-threshold functions is studied using harmonic analysis, and the results are used to derive lower bounds related to AC/sup 0/ functions. A Boolean function is polynomial threshold if it can be represented as a sign function of a sparse polynomial (one that consists of a polynomial number of terms). The main result is that polynomial-threshold functions can be characterized by means of their spectral representation. In particular, it is proved that a Boolean function whose L/sub 1/ spectral norm is bounded by a polynomial in n is a polynomial-threshold function, and that a Boolean function whose L/sub infinity //sup -1/ spectral norm is not bounded by a polynomial in n is not a polynomial-threshold function. Some results for AC/sup 0/ functions are derived. |

Year | DOI | Venue |
---|---|---|

1992 | 10.1137/0221003 | SFCS '90 Proceedings of the 31st Annual Symposium on Foundations of Computer Science |

Keywords | DocType | Volume |

polynomial threshold function,ac0 function,spectral norm,boolean functions,lower bound,neural networks,spectrum,computational modeling,polynomials,boolean function,circuits,harmonic analysis | Journal | 21 |

Issue | ISSN | ISBN |

1 | 0097-5397 | 0-8186-2082-X |

Citations | PageRank | References |

37 | 5.37 | 5 |

Authors | ||

2 |

Authors (2 rows)

Cited by (37 rows)

References (5 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Jehoshua Bruck | 1 | 3256 | 374.15 |

Roman Smolensky | 2 | 118 | 14.12 |