arXiv:2611.13787 · v1

Local Modifications of Nearest-Neighbor and Min-Plus Representations

首次提交 2026-11-10 17:22

版本更新 2026-11-10 17:22

雷达观测 2026-11-11 11:04

摘要

We study how changing a Boolean-valued function at $d$ inputs affects the size and precision of its exact representations. Starting from a representation of size $m$, we prove four bounds, two for nearest-neighbor (NN) representations and two for integer min-plus representations. (i) For NN representations on a finite subset of $\mathbb{R}^n$ with $n\ge2$, at most $m+2d$ anchors suffice. The coefficient $2$ is optimal: on a three-point domain, changing one value can increase the minimum number of anchors from one to three. (ii) For NN representations on the Boolean cube with rational anchors, let $R$ be the maximum original coordinate bit length, and let $Δ$ be the maximum bit length of the least common denominator of any one original anchor's coordinates. We construct a representation with at most $m+3d$ anchors on a common dyadic grid and coordinate bit length $O(R+Δ+\log(n+1))$. (iii) For integer min-plus representations on the Boolean cube, we give a construction that keeps the original $m$ forms and their labels and adds at most $d$ new forms. Its maximum weight is at most $W+2n$, where $W$ is the largest absolute original coefficient, including constant terms. (iv) For integer min-plus representations on a finite rational domain $X\subset\mathbb{Q}^n$, at most $m+2d$ forms suffice. Their maximum weight is polynomially bounded in $m,d,W,n,|X|$, the coordinate bound, and the common denominator of $X$. The coefficient $2$ is again optimal: on a three-point domain, changing one value can increase the minimum number of forms from one to three. These bounds imply stability under polynomially many changes on the cube for polynomial-size representations, including those with polynomially bounded NN coordinate bit length or min-plus weight.

作者备注：19 pages, 2 figures