Local Algorithms on Sparse Random Graphs

Mute
Current Time 0:00
/
Duration Time 0:00
Loaded: 0%
Progress: 0%
Stream TypeLIVE
Remaining Time -0:00
 

Description of video

Date: 2/23/23
Speaker :Csóka Endre

Keywords

    We examine the structures and phase transitions in large random graphs. For example, the structure of a largest independent set in a random d-regular graph on n→∞ vertices is in a "solid state" for d≥20 but probably in a "spin glass state" for d≤19 . We are using the tools of graph limit theory, local algorithms (IID-factor processes), and probability theory, and we are trying to translate and extend some intuitive arguments in statistical physics into this mathematical language.

    Downloads