Among various algorithms designed to exploit the specific properties of quantum computers
with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to …

Heuristic methods are used when rigorous ones are either unknown or cannot be applied,
typically because they would be too slow. A metaheuristic is a general optimization …

Researchers currently use a number of approaches to predict and substantiate information-
computation gaps in high-dimensional statistical estimation problems. A prominent …

We study both classical and quantum algorithms to solve a hard optimization problem,
namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy …

We establish that in the large degree limit, the value of certain optimization problems on
sparse random hypergraphs is determined by an appropriate Gaussian optimization …

We rigorously determine the exact freezing threshold, rkf, for k-colourings of a random
graph. We prove that for random graphs with density above rkf, almost every colouring is …

Let A be a random m× n matrix over the finite field F _q F q with precisely k non-zero entries
per row and let y ∈ F _q^ my∈ F qm be a random vector chosen independently of A. We …

The last decade witnessed several pivotal results on random inference problems where the
aim is to learn a hidden ground truth from indirect randomised observations; much of this …

We consider random systems of linear equations over GF (2) in which every equation binds
k variables. We obtain a precise description of the clustering of solutions in such systems. In …

We determine the rank of a random matrix A over an arbitrary field with prescribed numbers
of non-zero entries in each row and column. As an application we obtain a formula for the …