On the Complexity of Computing with p-adic Lattices
We study the complexity of two fundamental problems attached to p-adic lattices: computing an N-orthogonal basis, and deciding whether a given basis is N-orthogonal. When the norm is supplied through an explicit diagonal representation, both problems are polynomial. However, in the black-box model, where the ultrametric norm N is fixed and only accessible through an evaluation oracle, we prove that both problems require $Ω$(p^{v-1} ) queries in the worst case, where v $\le$ n is the largest multiplicity of a commensurability class of N and n is the dimension of the ambient vector space. We…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.38535
curl -X POST /api/v1/records/arxiv/2610.38535/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.38535/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'