För att formellt förstå kraften i neural computing, måste vi först bryta gränsen av tröskelkretsar med två och tre lager, en regim som har varit förvånansvärt svår att analysera. Vi bevisar den första superlinjära grindens nedre gränser och den första superquadratiska trådens nedre gränser för djup-två linjära tröskelkretsar med godtyckliga vikter, och djup-tre majoritetskretsar som beräknar en explicit funktion. • Vi bevisar att för alla ε log(n)/n, den linjära tiden beräkningsbara Andreev funktion inte kan beräknas på en (1/2 + ε)-fraktion av n-bit ingångar genom djup-två kretsar av o(ε 3 n 3/2 / log 3 n) grindar, inte heller kan det beräknas med o(ε 3 n 5/2 / log 7/2 n) ledningar. Detta etablerar en genomsnittlig "storlekshierarki" för tröskelkretsar, eftersom Andreevs funktion kan beräknas genom enhetliga djup-två kretsar av o(n 3 ) linjära tröskelgrindar, och genom enhetliga djup-tre kretsar av O(n) majoritetsgrindar. • Vi presenterar en ny funktion i P baserad på småskaliga uppsättningar, som vi bevisar inte kan beräknas med en majoritet av djup-två tröskelkretsar av o(n 3/2 / log 3 n) grindar, inte heller med o(n 5/2 / log 7/2 n) ledningar. • Vi ger snäva genomsnittliga-case (gate och wire) komplexa resultat för beräkning Parity med djup-två tröskelkretsar; svaret visar sig vara samma som för djup-två majoritet kretsar. Nyckeln är en ny metod för att analysera slumpmässiga begränsningar av linjära tröskelfunktioner. Vårt huvudsakliga analysverktyg är Littlewood-Offord Lemma från additiv kombinatorik.
Med hjälp av slumpmässiga begränsningar, Kane och Williams REF bevisade att alla THR • THR kretsar dator Andreev funktion kräver.(n 1.5 ) grindar och  på 2.5 ) ledningar.
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}