research
∙
01/23/2023
The k-XORSAT threshold revisited
We provide a simplified proof of the random k-XORSAT satisfiability thre...
share
research
∙
06/15/2022
Statistical and Computational Phase Transitions in Group Testing
We study the group testing problem where the goal is to identify a set o...
research
∙
05/17/2022
On the Hierarchy of Distributed Majority Protocols
We study the Consensus problem among n agents, defined as follows. Initi...
research
∙
02/11/2022
Metastability of the Potts ferromagnet on random regular graphs
We study the performance of Markov chains for the q-state ferromagnetic ...
research
∙
12/28/2021
The full rank condition for sparse random matrices
We derive a sufficient condition for a sparse random matrix with given n...
research
∙
11/04/2020
Belief Propagation on the random k-SAT model
Corroborating a prediction from statistical physics, we prove that the B...
research
∙
09/22/2020
The Ising antiferromagnet and max cut on random regular graphs
The Ising antiferromagnet is an important statistical physics model with...
research
∙
07/15/2020
Inference and mutual information on random factor graphs
Random factor graphs provide a powerful framework for the study of infer...
research
∙
02/10/2020
The random 2-SAT partition function
We show that throughout the satisfiable phase the normalised number of s...
research
∙
11/06/2019
Optimal non-adaptive group testing
In non-adaptive group testing we aim to identify a small set of k∼ n^θ i...
research
∙
06/13/2019
The rank of sparse random matrices
Generalising prior work on the rank of random matrices over finite field...
research
∙
05/31/2019
The cut metric for probability distributions
Guided by the theory of graph limits, we investigate a variant of the cu...
research
∙
02/06/2019
Information-theoretic and algorithmic thresholds for group testing
In the group testing problem we aim to identify a small number of infect...
research
∙
12/23/2018
Lower bounds on the chromatic number of random graphs
We prove that a formula predicted on the basis of non-rigorous physics a...
research
∙
10/17/2018
The rank of random matrices over finite fields
We determine the rank of a random matrix A over a finite field with pres...
research
∙
02/26/2018
The replica symmetric phase of random constraint satisfaction problems
Random constraint satisfaction problems play an important role in comput...
research
∙
10/20/2017
The satisfiability threshold for random linear equations
Let A be a random m× n matrix over the finite field F_q with precisely k...
research
∙
06/25/2007