Guest column
Files
Accepted manuscript
Date
2020-12-14
Authors
Bun, Mark
Thaler, Justin
Version
Accepted manuscript
OA Version
Citation
M. Bun, J. Thaler. 2020. "Guest Column." ACM SIGACT News, Volume 51, Issue 4, pp. 48 - 72. https://doi.org/10.1145/3444815.3444825
Abstract
The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This article surveys what we know about approximate degree and illustrates some of its applications in theoretical computer science.