Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials
© Richard Ryan Williams; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018). We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over ℝ) of functions from some "simple" class C. In parti...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137318 |
| _version_ | 1826210897447616512 |
|---|---|
| author | Williams, Richard Ryan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Williams, Richard Ryan |
| author_sort | Williams, Richard Ryan |
| collection | MIT |
| description | © Richard Ryan Williams; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018). We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over ℝ) of functions from some "simple" class C. In particular, given C we are interested in finding low-complexity 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 well-understood 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 low-degree polynomials over a finite field, all of which are well-studied 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 "semi-explicit" Boolean functions. Let α(n) be an unbounded function such that nα(n) is time constructible (e.g. α(n) = log∗(n)). We show: Functions in NTIME[nα(n)] that require super-polynomially many linear threshold functions to represent (depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds). Functions in NTIME[nα(n)] that require super-polynomially many ReLU gates to represent (depth-two neural networks with ReLU activation function). Functions in NTIME[nα(n)] that require super-polynomially many O(1)-degree Fp-polynomials to represent exactly, for every prime p (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in E requiring 2Ω(n) linear combinations. Functions in NTIME[npoly(logn)] that require super-polynomially many ACC • THR circuits to represent exactly (further generalizing the recent lower bounds of Murray and the author). We also obtain "fixed-polynomial" 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. |
| first_indexed | 2024-09-23T14:57:32Z |
| format | Article |
| id | mit-1721.1/137318 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:57:32Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1373182023-04-14T16:28:42Z Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials Williams, Richard Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Richard Ryan Williams; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018). We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over ℝ) of functions from some "simple" class C. In particular, given C we are interested in finding low-complexity 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 well-understood 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 low-degree polynomials over a finite field, all of which are well-studied 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 "semi-explicit" Boolean functions. Let α(n) be an unbounded function such that nα(n) is time constructible (e.g. α(n) = log∗(n)). We show: Functions in NTIME[nα(n)] that require super-polynomially many linear threshold functions to represent (depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds). Functions in NTIME[nα(n)] that require super-polynomially many ReLU gates to represent (depth-two neural networks with ReLU activation function). Functions in NTIME[nα(n)] that require super-polynomially many O(1)-degree Fp-polynomials to represent exactly, for every prime p (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in E requiring 2Ω(n) linear combinations. Functions in NTIME[npoly(logn)] that require super-polynomially many ACC • THR circuits to represent exactly (further generalizing the recent lower bounds of Murray and the author). We also obtain "fixed-polynomial" 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. 2021-11-04T11:54:13Z 2021-11-04T11:54:13Z 2018 2021-03-30T15:00:53Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137318 Williams, Richard Ryan. 2018. "Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials." Leibniz International Proceedings in Informatics, LIPIcs, 102. en 10.4230/LIPIcs.CCC.2018.6 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Williams, Richard Ryan Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials |
| title | Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials |
| title_full | Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials |
| title_fullStr | Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials |
| title_full_unstemmed | Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials |
| title_short | Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials |
| title_sort | limits on representing boolean functions by linear combinations of simple functions thresholds relus and low degree polynomials |
| url | https://hdl.handle.net/1721.1/137318 |
| work_keys_str_mv | AT williamsrichardryan limitsonrepresentingbooleanfunctionsbylinearcombinationsofsimplefunctionsthresholdsrelusandlowdegreepolynomials |