{"id":"arxiv/2602.10922","url":"https://arxiv.org/abs/2602.10922","tags":["cs.CG","cs.DM","cs.DS","math.CO"],"score":0,"title":"Implicit representations via the polynomial method","domain":"cs.CG","source":"arxiv","authors":["Jean Cardinal","Micha Sharir"],"reviews":0,"subject":"cs.CG","summary":"Semialgebraic graphs are graphs whose vertices are points in $\\mathbb{R}^d$, and adjacency between two vertices is determined by the truth value of a semialgebraic predicate of constant complexity. We show how to harness polynomial partitioning methods to construct compact adjacency labeling schemes for families of semialgebraic graphs. That is, we show that for any family of semialgebraic graphs, given a graph on $n$ vertices in this family, we can assign a label consisting of $O(n^{1-2/(d+1) + \\varepsilon})$ bits to each vertex (where $\\varepsilon > 0$ can be made arbitrarily small and the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-11","reactions":{}}