Norm-Query Complexity of Algorithmic Problems in Finite-Dimensional p-adic Normed Spaces
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.22084
curl -X POST /api/v1/records/arxiv/2608.22084/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.22084/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'