Unité de Mathématiques Pures et Appliquées

Topological complexity of spiked random polynomials and finite-rank spherical integrals

We study the annealed complexity of Gaussian random homogeneous polynomials on the (N−1)-dimensional unit sphere in the presence of deterministic perturbations depending on fixed orthonormal vectors and external parameters. We derive variational formulas for the exponential asymp...

Critical point representation of the mutual information in the sparse stochastic block model

We consider the problem of recovering the community structure in the stochastic block model. We aim to describe the mutual information between the observed network and the actual community structure as the number of nodes diverges while the average degree of a given node remains...

PRISM with a Pinch of Salt: Simple, Efficient, and Strongly Unforgeable Signatures from Isogenies

Abstract The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose securi...