Unbounded Violations of the Square-Root Degree Bound
We disprove the Gopalan–Servedio square-root conjecture, even up to an arbitrary constant factor. For every real C > 0, there is a nonconstant Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ on a finite sign cube such that $\displaystyle \sum_{i=1}^n \widehat f(\{i\})\gt C\sqrt{\deg(f)}.$ Here $\widehat f(\{i\})$ is the linear Fourier coefficient associated with the i th input, and $\deg(f)$ is the degree of the real multilinear polynomial representing f .
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Unbounded-Violations-of-the-Square-Root-Degree-Bound
curl -X POST /api/v1/records/openai-math/Unbounded-Violations-of-the-Square-Root-Degree-Bound/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Unbounded-Violations-of-the-Square-Root-Degree-Bound/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'