Abstract
We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over R) of functions from some "simple" class C. In particular, given C we are interested in finding lowcomplexity functions lacking sparse representations. When C forms a basis for the space of Boolean functions (e.g., the set of PARITY functions or the set of conjunctions) this sort of problem has a wellunderstood answer; the problem becomes interesting when C is "overcomplete" and the set of functions is not linearly independent. We focus on the cases where C is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of lowdegree polynomials over a finite field, all of which are wellstudied in different contexts.
We provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for "semiexplicit" Boolean functions. Let alpha(n) be an unbounded function such that n^{alpha(n)} is time constructible (e.g. alpha(n) = log^*(n)). We show:
 Functions in NTIME[n^{alpha(n)}] that require superpolynomially many linear threshold functions to represent (depthtwo neural networks with sign activation function, a special case of depthtwo threshold circuit lower bounds).
 Functions in NTIME[n^{alpha(n)}] that require superpolynomially many ReLU gates to represent (depthtwo neural networks with ReLU activation function).
 Functions in NTIME[n^{alpha(n)}] that require superpolynomially many O(1)degree F_ppolynomials to represent exactly, for every prime p (related to problems regarding HigherOrder "Uncertainty Principles"). We also obtain a function in E^{NP} requiring 2^{Omega(n)} linear combinations.
 Functions in NTIME[n^{poly(log n)}] that require superpolynomially many ACC ° THR circuits to represent exactly (further generalizing the recent lower bounds of Murray and the author). We also obtain "fixedpolynomial" lower bounds for functions in NP, for the first three representation classes. All our lower bounds are obtained via algorithms for analyzing linear combinations of simple functions in the above scenarios, in ways which substantially beat exhaustive search.
BibTeX  Entry
@InProceedings{williams:LIPIcs:2018:8884,
author = {Richard Ryan Williams},
title = {{Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and LowDegree Polynomials}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {6:16:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8884},
URN = {urn:nbn:de:0030drops88846},
doi = {10.4230/LIPIcs.CCC.2018.6},
annote = {Keywords: linear threshold functions, lower bounds, neural networks, lowdegree polynomials}
}
Keywords: 

linear threshold functions, lower bounds, neural networks, lowdegree polynomials 
Collection: 

33rd Computational Complexity Conference (CCC 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 