MetadataShow full item record
Citation (published version)M. Bun, J. Thaler. 2020. "Guest Column." ACM SIGACT News, Volume 51, Issue 4, pp. 48 - 72. https://doi.org/10.1145/3444815.3444825
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.