Thesis supervisor: Gábor Pete
Location of studies (in Hungarian): Department of Stochastics, Institute of Mathematics, BME Abbreviation of location of studies: BME
Description of the research topic:
Noise-sensitivity of a Boolean function with iid random input bits means that resampling a tiny proportion of the input makes the output unpredictable. This notion arises naturally in computer science, but perhaps the most striking example comes from statistical physics, in large part due to the work of the supervisor: the macroscopic geometry of planar percolation is very sensitive to noise. This can be recast in terms of Fourier analysis on the hypercube: a function is noise sensitive if most of its Fourier weight is on “high energy” eigenfunctions of the random walk operator.
The focus of the current research of the supervisor is on applying such ideas in a variety of settings, and the PhD student would take part in these efforts. Here are some key sample problems:
Problem 1: Prove noise sensitivity results for interesting Boolean functions with iid input bits coming from computer science or statistical physics, such as First Passage Percolation. What is the exact relationship between noise sensitivity and different computational complexity measures?
Problem 2: For Glauber dynamics of the Ising model on any finite transitive graph at its critical temperature, is it true that total magnetization is the observable that mixes the most slowly? What are the observables that get mixed much faster? This is interesting even on the complete graph, called the Curie-Weiss model. Another key example is the 2-dimensional critical Ising model, where conformal invariant techniques may be applied.
Problem 3: The Interchange Process on a graph with n vertices is the following random walk on the permutation group Sym(n): we start with a different particle at each vertex, and at each step of the walk, we interchange the two particles at a uniformly chosen random edge of the graph. Understand the mixing time of this random walk. How much time is needed to get macroscopic cycles in the resulting random permutation? Relate these questions to the representation theory of Sym(n).
Problem 4: Study the behavior of statistical physics models along Benjamini-Schramm convergent graph sequences. When is the critical temperature determined by the local structure?
Required language skills: english Further requirements: An MSc degree in mathematics, with a very strong background in probability and stochastic processes is a must. Strong background in combinatorics or group theory or complex analysis is welcome.
Login
