Abstrakt. Analysen av linjär tröskel Booleska funktioner har nyligen uppmärksammats av dem som är intresserade av kretsens komplexitet samt av dem som är intresserade av neurala nätverk. Här definieras en generalisering av linjära tröskelfunktioner, nämligen polynomiska tröskelfunktioner, och dess förhållande till klassen linjära tröskelfunktioner undersöks. En boolesk funktion är polynomtröskel om den kan representeras som en teckenfunktion hos ett polynom som består av ett polynom (i antalet variabler) antal termer. Det huvudsakliga resultatet av detta papper visar att klassen av polynom tröskelfunktioner (som kallas PT1 är strikt innesluten i klassen av booleska funktioner som kan beräknas med ett djup 2, obundna fan-in polynom storlek krets linjär tröskel grindar (som kallas LT2). Harmonisk analys av booleska funktioner används för att härleda ett nödvändigt och tillräckligt villkor för att en funktion ska vara en S-tröskelfunktion för en given uppsättning S-monomialer. Detta villkor används för att visa att antalet olika S-tröskelfunktioner, för en given S, är högst 2 t'/ 1) l. På grundval av det nödvändiga och tillräckliga villkoret härleds en lägre gräns på antalet termer i en tröskelfunktion. Den nedre gränsen uttrycks i termer av spektral representation av en boolesk funktion. Det har konstaterats att booleska funktioner som har ett exponentiellt litet spektrum inte är polynomtröskel. En familj av funktioner visas som har ett exponentiellt litet spektrum; de kallas "semibent" funktioner. En funktion är konstruerad som är både semibent och symmetrisk för att bevisa att PT är korrekt innesluten i LT2. I hela detta papper kommer en boolesk funktion att definieras som f" { 1, -1}" { 1, -1}; nämligen 0 och representeras av respektive -1. Det antas också, utan förlust av allmängiltighet, att F(X) :/: 0 för alla X. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning.
Bruck REF studerade polynomiska tröskelfunktioner, och visade att sådana funktioner kan beräknas genom djup-2 polynomiska stora kretsar med obegränsade linjära tröskelportar för fläktar.
Harmonic Analysis of polynomial threshold functions
{'venue': 'SIAM Journal of Discrete Mathematics', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}