Post by Centrum Wiskunde & Informatica

What can phase transitions tell us about algorithms, networks and random structures? More than you might think. This week, CWI and partner universities hosted the first workshop of the PhaseCAP Research Semester Programme, bringing together an international group of researchers from combinatorics, algorithms and probability. The challenges were, among others: how do we understand the underlying structure of a large-scale network, and which local constraints shape an algorithm’s running time? PhaseCAP approaches these questions through ideas inspired by statistical physics. And that lens is proving productive - not only in theory, but also in the conversations it creates. As organizer Noela Müller observed: “We have here a rather diverse mixture of participants like experts in algorithms, combinatorics and more pure probabilists, and we have a really nice interaction.” Organizer Serte Donderwinkel added: “Many groups have formed with people that have never done collaborations together before on this. And now they are starting to work together”. The scientific discussions ranged from random graphs to detection problems. As Donderwinkel noted, participants explored, for instance, how you can distinguish one random model from another random model by adding structure, and that “seeing that this structure exists is often quite a lot easier than pointing out where it is”. Another highlight of the week were the plenary lectures by Tom Bohman (Carnegie Mellon University) and Christina Goldschmidt (University of Oxford), which were open to a broader audience. Many thanks to the organizers - Ferenc Bencs, Jop Briët, Serte Donderwinkel, Carla Groenland, Ross Kang, Noela Müller and Guus Regts, and to all participants from across Europe, the US, Asia and beyond. Follow CWI for more information on the Research Semester Programmes. 📚 Group picture: CWI/Paul Roberts. #Combinatorics #Algorithms #Probability #NetworkScience #StatisticalPhysics