OURAGAN: Outils de Résolution Algébriques pour la Géométrie et ses Applications

Abstract In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated cosets of overlattices. The key idea is hence no longer to work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in an overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case. This new approach allows us to solve not only shortest vector problems, but also closest vector problems, in lattices of dimension $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}n$ in time $2^{0.3774\, n}$ using memory $2^{0.2925\, n}$ . Moreover, the algorithm is straightforward to parallelize on most computer architectures.

We show that the figure-eight knot complement admits a uniformizable spherical CR structure, ie it occurs as the manifold at infinity of a complex hyperbolic orbifold. The uniformization is unique provided we require the peripheral subgroups to have unipotent holonomy. 32V05, 57M50;

We present a scheme for a universal device which can be programed by quantum states to approximate a chosen projective measurement to a given precision. Our scheme can be viewed as an extension of the swap test to the instance where one state is supplied many times. As such, it has many potential applications given the variety of quantum information tasks which make use of the swap test. In particular, we show that our scheme is optimal for state discrimination under the one-sided error requirement, and optimally approximates any projective measurement. Furthermore, we propose a practical implementation of our scheme with passive linear optics, which involves a simple interferometer composed only of balanced beam splitters.

In this paper, we present new computer algebra based methods for testing the structural stability of n-D discrete linear systems (with n ≥ 2). More precisely, starting from the usual stability conditions which resumes to deciding if an hypersurface has points in the unit polydisk, we show that the problem is equivalent to deciding if an algebraic set has real points and use state-of-the-art algorithms for this purpose. Our strategy has been implemented in Maple and its relevance demonstrated through numerous experimentations.

We present a method for solving two minimal problems for relative camera pose estimation from three views, which are based on three view correspondences of (i) three points and one line and (ii) three points and two lines through two of the points. These problems are too difficult to be efficiently solved by the state of the art Grobner basis methods. Our method is based on a new efficient homotopy continuation (HC) solver, which dramatically speeds up previous HC solving by specializing HC methods to generic cases of our problems. We show in simulated experiments that our solvers are numerically robust and stable under image noise. We show in real experiment that (i) SIFT features provide good enough point-and-line correspondences for three-view reconstruction and (ii) that we can solve difficult cases with too few or too noisy tentative matches where the state of the art structure from motion initialization fails.

We give a description of several representation varieties of the fundamental group of the complement of the figure eight knot in PGL (3, ℂ) or PSL (3, ℂ). We obtain a description of the projection of the representation variety into the character variety of the boundary torus into SL (3, ℂ).

Let M be a noncompact hyperbolic 3-manifold that has a triangulation by positively oriented ideal tetrahedra. We explain how to produce local coordinates for the variety defined by the gluing equations for -representations. In particular, we prove local rigidity of the “geometric” representation in , recovering a recent result of Menal-Ferrer and Porti. More generally, we give a criterion for local rigidity of -representations and provide detailed analysis of the figure-eight-knot sister manifold exhibiting the different possibilities that can occur.

International audience

This paper presents MQ on my Mind (MQOM), a digital signature scheme based on the difficulty of solving multivariate systems of quadratic equations (MQ problem). MQOM has been submitted to the NIST call for additional post-quantum signature schemes. MQOM relies on the MPC-in-the-Head (MPCitH) paradigm to build a zero-knowledge proof of knowledge (ZK-PoK) for MQ which is then turned into a signature scheme through the Fiat-Shamir heuristic. The underlying MQ problem is non-structured in the sense that the system of quadratic equations defining an instance is drawn uniformly at random. This is one of the hardest and most studied problems from multivariate cryptogra-phy which hence constitutes a conservative choice to build candidate post-quantum cryptosystems. For the efficient application of the MPCitH paradigm, we design a specific MPC protocol to verify the solution of an MQ instance. Compared to other multivariate signature schemes based on non-structured MQ instances, MQOM achieves the shortest signatures (6.3-7.8 KB) while keeping very short public keys (few dozen of bytes). Other multivariate signature schemes are based on structured MQ problems (less conservative) which either have large public keys (e.g UOV) or use recently proposed variants of these MQ problems (e.g. MAYO).

Given two coprime polynomials $P$ and $Q$ in $\Z[x,y]$ of degree bounded by $d$ and bitsize bounded by $\tau$, we address the problem of solving the system $\{P,Q\}$. We are interested in certified numerical approximations or,more precisely, isolating boxes of the solutions. We are also interested in computing, as intermediate symbolic objects, rational parameterizations of he solutions, and in particular Rational Univariate Representations (RURs), which can easily turn many queries on the system into queries on univariate polynomials. Such representations require the computation of a separating form for the system, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. We present new algorithms for computing linear separating forms, RUR decompositions and isolating boxes of the solutions. We show that these three algorithms have worst-case bit complexity $\widetilde{O}_B(d^6+d^5\tau)$, where $\widetilde{O}$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to thebit complexity. We also present probabilistic Las-Vegas variants of our two first algorithms, which have expected bit complecity $\widetilde{O}_B(d^5+d^4\tau)$. A key ingredient of our proofs of complexity is an amortized analysis of the triangular decomposition algorithm via subresultants, which is of independent interest.

International audience

International audience

Abstract We introduce and study the class of semidefinite games, which generalizes bimatrix games and finite N -person games, by replacing the simplex of the mixed strategies for each player by a slice of the positive semidefinite cone in the space of real symmetric matrices. For semidefinite two-player zero-sum games, we show that the optimal strategies can be computed by semidefinite programming. Furthermore, we show that two-player semidefinite zero-sum games are almost equivalent to semidefinite programming, generalizing Dantzig’s result on the almost equivalence of bimatrix games and linear programming. For general two-player semidefinite games, we prove a spectrahedral characterization of the Nash equilibria. Moreover, we give constructions of semidefinite games with many Nash equilibria. In particular, we give a construction of semidefinite games whose number of connected components of Nash equilibria exceeds the long standing best known construction for many Nash equilibria in bimatrix games, which was presented by von Stengel in 1999.

<p style='text-indent:20px;'>Since their introduction in 2004, Polynomial Modular Number Systems (PMNS) have become a very interesting tool for implementing cryptosystems relying on modular arithmetic in a secure and efficient way. However, while their implementation is simple, their parameterization is not trivial and relies on a suitable choice of the polynomial on which the PMNS operates. The initial proposals were based on particular binomials and trinomials. But these polynomials do not always provide systems with interesting characteristics such as small digits, fast reduction, etc. <p style='text-indent:20px;'>In this work, we study a larger family of polynomials that can be exploited to design a safe and efficient PMNS. To do so, we first state a complete existence theorem for PMNS which provides bounds on the size of the digits for a generic polynomial, significantly improving previous bounds. Then, we present classes of suitable polynomials which provide numerous PMNS for safe and efficient arithmetic.

In this paper we make a series of numerical experiments to support Greenberg’s <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -rationality conjecture, we present a family of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -rational biquadratic fields and we find new examples of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -rational multiquadratic fields. In the case of multiquadratic and multicubic fields we show that the conjecture is a consequence of the Cohen–Lenstra–Martinet heuristic and of the conjecture of Hofmann and Zhang on the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -adic regulator, and we bring new numerical data to support the extensions of these conjectures. We compare the known algorithmic tools and propose some improvements.

We study a class of two-variable polynomials called exact polynomials which contains $A$ -polynomials of knot complements. The Mahler measure of these polynomials can be computed in terms of a volume function defined on the vanishing set of the polynomial. We prove that the local extrema of the volume function are on the two-dimensional torus and give a closed formula for the Mahler measure in terms of these extremal values. This formula shows that the Mahler measure of an irreducible and exact polynomial divided by $\pi$ is greater than the amplitude of the volume function. We also prove a K-theoretic criterion for a polynomial to be a factor of an $A$ -polynomial and give a topological interpretation of its Mahler measure.

International audience

19 pages, 2 figures

Consciousness has been described as acting as a global workspace that integrates perception, imagination, emotion and action programming for adaptive decision making. The mechanisms of this workspace and their relationships to the phenomenology of consciousness need to be further specified. Much research in this area has focused on the neural correlates of consciousness, but, arguably, computational modeling can better be used toward this aim. According to the Projective Consciousness Model (PCM), consciousness is structured as a viewpoint-organized, internal space, relying on 3D projective geometry and governed by the action of the Projective Group as part of a process of active inference. The geometry induces a group-structured subjective perspective on an encoded world model, enabling adaptive perspective taking in agents. Here, we review and discuss the PCM. We emphasize the role of projective mechanisms in perception and the appraisal of affective and epistemic values as tied to the motivation of action, under an optimization process of Free Energy minimization, or more generally stochastic optimal control. We discuss how these mechanisms enable us to model and simulate group-structured drives in the context of social cognition and to understand the mechanisms underpinning empathy, emotion expression and regulation, and approach-avoidance behaviors. We review previous results, drawing on applications in robotics and virtual humans. We briefly discuss future axes of research relating to applications of the model to simulation- and model-based behavioral science, geometrically structured artificial neural networks, the relevance of the approach for explainable AI and human-machine interactions, and the study of the neural correlates of consciousness.

Metabolic networks and their reconstruction set a new era in the analysis of metabolic and growth functions in the various organisms. By modeling the reactions occurring inside an organism, metabolic networks provide the means to understand the underlying mechanisms that govern biological systems. Constraint-based approaches have been widely used for the analysis of such models and led to intriguing geometry-oriented challenges. In this setting, sampling uniformly points from polytopes derived from metabolic models (flux sampling) provides a representation of the solution space of the model under various conditions. However, the polytopes that result from such models are of high dimension (in the order of thousands) and usually considerably skinny. Therefore, to sample uniformly at random from such polytopes shouts for a novel algorithmic and computational framework specially tailored for the properties of metabolic models. We present a complete software framework to handle sampling in metabolic networks. Its backbone is a Multiphase Monte Carlo Sampling (MMCS) algorithm that unifies rounding and sampling in one pass, yielding both upon termination. It exploits an optimized variant of the Billiard Walk that enjoys faster arithmetic complexity per step than the original. We demonstrate the efficiency of our approach by performing extensive experiments on various metabolic networks. Notably, sampling on the most complicated human metabolic network accessible today, Recon3D, corresponding to a polytope of dimension $5\,335$, took less than $30$ hours. To the best of our knowledge, that is out of reach for existing software.