Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields

• URL: http://arxiv.org/abs/2203.06970v6
• Date: Tue, 12 Mar 2024 13:45:27 GMT
• Title: Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields
• Authors: Antoine Leudière, Pierre-Jean Spaenlehauer,
• Abstract summary: The Jacobian of an imaginary hyperelliptic curve defined over $mathbb F_q$ acts on a subset of isomorphism classes of Drinfeld modules. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. We prove that the problem of inverting the group action reduces the problem of finding isogenies of fixed $tau$-degree between Drinfeld $mathbb F_q[X]$-modules.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore algorithmic aspects of a simply transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian of an imaginary hyperelliptic curve defined over $\mathbb F_q$ acts on a subset of isomorphism classes of Drinfeld modules. We describe an algorithm to compute the group action efficiently. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. We report on an explicit computation done with our proof-of-concept C++/NTL implementation; it took a fraction of a second on a standard computer. We prove that the problem of inverting the group action reduces to the problem of finding isogenies of fixed $\tau$-degree between Drinfeld $\mathbb F_q[X]$-modules, which is solvable in polynomial time thanks to an algorithm by Wesolowski. We give asymptotic complexity bounds for all algorithms presented in this paper.

Related papers

• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems. We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Upper bounds for Grothendieck constants, quantum correlation matrices and CCP functions [0.0]
  We search for the still unknown exact value of the real and complex Grothendieck constant $K_GmathbbF$ in the famous Grothendieck inequality (unsolved since 1953) We also recover all famous upper bounds of Grothendieck himself ($K_GmathbbR leq sinh(pi/2) approx 2.301$), Krivine ($K_GmathbbR leq fracpi2 ln (1 + sqrt2)
  arXiv  Detail & Related papers  (2023-05-08T02:43:01Z)
• An Algorithm for Computing with Brauer's Group Equivariant Neural Network Layers [0.0]
  We present an algorithm for multiplying a vector by any weight matrix for each of these groups, using category theoretic constructions to implement the procedure. We show that our approach extends to the symmetric group, $S_n$, recovering the algorithm of arXiv:2303.06208 in the process.
  arXiv  Detail & Related papers  (2023-04-27T13:06:07Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Quantum information theory and Fourier multipliers on quantum groups [0.0]
  We compute the exact values of the minimum output entropy and the completely bounded minimal entropy of quantum channels acting on matrix algebras. Our results use a new and precise description of bounded Fourier multipliers from $mathrmL1(mathbbG)$ into $mathrmLp(mathbbG)$ for $1 p leq infty$ where $mathbbG$ is a co-amenable locally compact quantum group.
  arXiv  Detail & Related papers  (2020-08-27T09:47:10Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.