{
  "annotation_id": "513cf167-256f-45f7-8ccc-8506c938ec4e",
  "date_created": "2026-02-17T05:53:15.300000Z",
  "date_modified": "2026-02-17T05:53:15.300000Z",
  "file_hash": "a10382c1d36c0865d008827c8d0ff02ef2ef8c25e9d9c5f268d92fe6885f70ab",
  "private": false,
  "record": {
    "abstract": "We prove that $\\mathrm{deg}(f) \\leq 2 \\, \\mathrm{rdeg}(f)^4$ for every Boolean function $f$, where $\\mathrm{deg}(f)$ is the degree of $f$ and $\\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.",
    "arxiv_id": "2601.08727",
    "authors": [
      "Matt Kovacs-Deak",
      "Daochen Wang",
      "Rain Zimin Yang"
    ],
    "categories": [
      "cs.CC",
      "cs.DM",
      "quant-ph"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "Rational degree is polynomially related to degree",
    "url": "https://arxiv.org/abs/2601.08727",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "ac16c463-e266-4e44-bc27-e924497c6a83",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}