Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.03591 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916796391489536 |
|---|---|
| author | Ushakov, Alexander |
| author_facet | Ushakov, Alexander |
| contents | In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations $\prod_{i=1}^m z_i^{-1} c_i z_i = 1$ (and its variants) over the class of finite metabelian groups $G_{p,n}=\mathbb{Z}_p^n \rtimes \mathbb{Z}_p^\ast$, where $n\in\mathbb{N}$ and $p$ is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03591 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constrained inhomogeneous spherical equations: average-case hardness Ushakov, Alexander Group Theory 20F16, 20F10, 68W30 In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations $\prod_{i=1}^m z_i^{-1} c_i z_i = 1$ (and its variants) over the class of finite metabelian groups $G_{p,n}=\mathbb{Z}_p^n \rtimes \mathbb{Z}_p^\ast$, where $n\in\mathbb{N}$ and $p$ is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case). |
| title | Constrained inhomogeneous spherical equations: average-case hardness |
| topic | Group Theory 20F16, 20F10, 68W30 |
| url | https://arxiv.org/abs/2405.03591 |