Vi anser att problemet med att representera Booleska funktioner exakt genom "sparse" linjära kombinationer (över R) av funktioner från vissa "enkel" klass C. Särskilt, med tanke på C är vi intresserade av att hitta lågkomplexitet funktioner saknar glesa representationer. När C är uppsättningen av PARITY funktioner eller uppsättningen av associationer, denna typ av problem har ett välförståeligt svar; problemet blir intressant när C är "överfullständig" och uppsättningen funktioner är inte linjärt oberoende. Vi fokuserar på de fall där C är uppsättningen av linjära tröskelfunktioner, uppsättningen av rättade linjära enheter (ReLUs), och uppsättningen av låggradiga polynom över ett ändligt fält, som alla är välstuderade i olika sammanhang. Vi bygger på den nya enkla vittne lemma Cody Murray och författaren, ger vi generiska verktyg för att bevisa lägre gränser på representationer av detta slag. Genom att tillämpa dessa ger vi flera nya nedre gränser för "semi-explicit" Booleska funktioner. Låt α(n) vara en obunden funktion så att n α(n) är tidskonstruerad (t.ex. α(n) = log  på (n)). Vi visar: • Funktioner i NTIME[n α(n) ] som kräver super-polynomiskt många linjära tröskelfunktioner för att representera (djup-två neurala nätverk med teckenaktiveringsfunktion, ett specialfall av djup-två tröskelkrets nedre gränser). • Funktioner i NTIME[n α(n) ] som kräver super-polynomiskt många ReLU grindar för att representera (djup två neurala nätverk med ReLU aktiveringsfunktion). • Funktioner i NTIME[n α(n) ] som kräver super-polynomiskt många O(1)-grad F p -polynomials att representera exakt, för varje prime p (relaterat till problem med högre-Order Osäkerhet Principer). Vi får också en funktion i E NP som kräver 2 (n) -storlek linjära kombinationer. • Funktioner i NTIME[n poly(log n) ] som kräver super-polynomiskt många ACC • THR kretsar av polynom storlek för att representera exakt (ytterligare generalisera de senaste lägre gränserna för Murray och författaren). Vi får också "fixed-polynomial" nedre gränser för funktioner i NP, för de första tre representation klasser.
Senast visade Williams REF att det finns funktioner i NQP som inte kan representeras av en linjär kombination av polynomiskt många ACC • THR-kretsar.
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}