Limits on representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials

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...

Full description

Bibliographic Details
Main Author: Williams, Richard Ryan
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: 2021
Online Access:https://hdl.handle.net/1721.1/137318

Similar Items

Similar Items