Research

This paper is available here. 

In collaboration with Remco van der Hofstad and Noela Müller,  studied the Erdős–Rényi graph Gn with edge probability d/n, where nonzero weights are assigned to the edges according to an arbitrary symmetric matrix Jn with nonzero elements. We show that the normalized rank of the weighted adjacency matrix of (Gn)n≥1, where 1s in the adjacency matrix are replaced by the edge weights, converges to a constant. 

Our results demonstrate that for the general class of sparse symmetric matrices under consideration, the asymptotics of the normalized rank are independent of the edge weights and even the underlying field.

This paper is available here. 

In this paper, together with Arnab Chatterjee, Amin Coja-Oghlan, Noela Müller, Connor Riddlesden, Maurice Rolvien, and Pavel Zakharov, we proved that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. 

This result implies that the logarithm of the number of satisfying assignments exhibits fluctuations of order √n, where n is the number of variables. Moreover, the variance of these fluctuations can be evaluated effectively. By contrast, for many other random constraint satisfaction problems, the typical fluctuations of the logarithm of the number of solutions remain bounded throughout all or most of the satisfiable regime.

This paper is available here.

In group testing, the objective is to identify defective items by testing groups of them together, while minimizing the number of tests. In this project, together with Lukas Hintze, Lena Krieg, and Olga Scheftelowitsch, we studied the case where each item is defective with a constant probability, independent of all other items. Furthermore, each test may produce false positive or false negative with a constant probability. 

We determine precise constants c such that cn log n tests are required to recover the infection status of all items, for both adaptive and non-adaptive group testing. The proofs in both cases either explicitly or implicitly use the idea of a genie-based estimator in community detection.

This paper is available here.

This is a follow-up project to Project 2. In this project, together with Noela Müller and Ralph Neininger, we demonstrated that the set of atoms in the limiting empirical marginal distribution of the random 2-SAT model is  Q ∩ (0, 1), for all clause-to-variable densities up to the satisfiability threshold. 

For densities, i.e., the number of variables divided by the number of clause, up to 1/2, the measure is purely discrete; however, for any density in (1/2, 1), we also establish the existence of a nontrivial continuous part. 

This paper is available here.

In this project, together with Remco van der Hofstad, we proved that the typical distances in a preferential attachment model without-degree m ≥ 2 and strictly positive fitness parameter are close to logν n, where ν is the exponential growth parameter of the local limit of the preferential attachment model. 

The proof relies on a path-counting technique, the first- and second-moment methods, as well as a novel proof of the convergence of the spectral radius of the offspring operator under a certain truncation. 

This paper is available here.

This is a follow-up project to Project 5. In this project, together with Hang Du, Shuyang Gong and Zhangsong Li, we study the asymptotic diameter of the preferential attachment model with parameters m≥2 and δ>0, and prove that the diameter of this preferential attachment model is (1+o(1))logνn with high probability, where ν is the exponential growth rate of the local weak limit of the preferential attachment mode.

Our proof follows a general recipe that relates the diameter of a random graph to its typical distance, which we expect to have applicability in a broader range of models.