The combination of random graphs methodology and ideas from statistical physics has proved immensely powerful in the study of various theoretical and applied problems. In this project, we plan to further explore connections between concepts from statistical mechanics, random graphs and algorithmic problems in specific settings. This exploration will be guided by questions such as: What can be said about the solution space of the algorithmic assignments, and how do these correspond to phase transitions in the system? What are the right observables to describe such phase transitions, and how do such observables scale in the near-critical regimes? Problems of interest include, but are not restricted to, the solution space of random linear equations, k-SAT assignment problems, as well as Ising and Potts models. Our first focus will lie on the rank of adjacency matrices of Erdös-Rényi random graphs over general fields, where methods originating from random constraint satisfaction problems have proved to be highly effective for the field of the rationals. Does this also hold for general finite fields?
|Supervisors||Remco van der Hofstad (TU/e) and Noela Müller (TU/e)|
|PhD Student||AHaodong Zhu|
|Location||Eindhoven University of Technology (TU/e)|