{"id":"arxiv/2608.22084","url":"https://arxiv.org/abs/2608.22084","tags":["cs.CC","math.NT"],"score":0,"title":"Norm-Query Complexity of Algorithmic Problems in Finite-Dimensional p-adic Normed Spaces","domain":"cs.CC","source":"arxiv","authors":["Zhefan Duan","Huawei Wu"],"reviews":0,"subject":"cs.CC","summary":"We study the deterministic norm-query complexity of computational problems in finite-dimensional vector spaces over $\\mathbb{Q}_p$ equipped with an arbitrary ultrametric norm. For orthogonalization, we prove that no uniform finite query bound depending only on the dimension exists: for every deterministic algorithm that produces an $N$-orthogonal basis for every ultrametric norm $N$, the number of norm queries is unbounded as $N$ varies. We then study the Longest Vector Problem (LVP) for a rank-$m$ $p$-adic lattice. By adapting a brute-force search to the general norm-query setting and…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-22","reactions":{}}