Constrained inhomogeneous spherical equations: average-case hardness
Let \(p\) be a prime, \(n \in \mathbb{N}\) and let \(G_{p,n}=\mathbb{Z}^{n}_{p} \rtimes \mathbb{Z}^{\times}_{p}\), where the action of \(\mathbb{Z}^{\times}_{p}\) on \(\mathbb{Z}^{n}_{p}\) is given by \((x_{1}, \ldots, x_{n}) \mapsto (\alpha x_{1}, \ldots, \alpha x_{n})\), the multiplication by an element \(\alpha \in \mathbb{Z}^{\times}_{p}\).\N\NIn the paper under review, the author analyzes 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\) over the class of finite metabelian groups \(G_{p,n}\). Assuming that some lattice approximation problem is hard in the worst case, he proves that the problem of finding solutions for certain constrained spherical equations is computationally hard on average.
- A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
- A sieve algorithm for the shortest lattice vector problem
- Commutator width in the first Grigorchuk group
- scientific article; zbMATH DE number 3750287 (Why is no real title available?)
- scientific article; zbMATH DE number 46357 (Why is no real title available?)
- scientific article; zbMATH DE number 88856 (Why is no real title available?)
- scientific article; zbMATH DE number 1256724 (Why is no real title available?)
- scientific article; zbMATH DE number 1088230 (Why is no real title available?)
- scientific article; zbMATH DE number 1408356 (Why is no real title available?)
- Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz
- Knapsack problems in products of groups
- Lattice problems in NP ∩ coNP
- On the limits of nonapproximability of lattice problems
- Orientable quadratic equations in free metabelian groups
- Quadratic equations in hyperbolic groups are NP-complete
- Quadratic equations in metabelian Baumslag–Solitar groups
- Quadratic equations in the Grigorchuk group.
- Quadratic equations over free groups and free products
- Satisfiability problems for finite groups
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
- Spherical quadratic equations in free metabelian groups.
- The complexity of solving equations over finite groups
- The complexity of the equation solvability and equivalence problems over finite groups
- The solvability problem for quadratic equations over free groups is NP-complete
- Using surfaces to solve equations in free groups
This page was built for publication: Constrained inhomogeneous spherical equations: average-case hardness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6601473)
