Postdoctoral Research Associate (PDRA) at the School of Informatics, University of Edinburgh.
Homepage: https://pw384.github.io

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Initiated by Valiant's definition of the complexity class #P, the study of counting problems has remained a fruitful line of research for nearly half a century. Yet a cornucopia of landmark results show how cross-disciplinary this field is beyond complexity theory, witness by not only the applications, but also the methodology. For instance, one main phenomenon is the so-called "computational phase transition", namely, a computational task may jump sharply from being tractable to intractable as some parameter crosses a critical threshold. Surprisingly, the computational phase transition can coincide with the real physical phase transition, as observed in many fundamental approximate counting problems.
In this talk, I will briefly postulate how old challenges in this line of research start to crumble with the emergence of recent techniques. I will also depict the landscape of new challenges arising from recent works that are left for us to tackle, in hope of interdisciplinary benefits.

Based on multiple papers with Konrad Anand (Queen Mary), Weiming Feng (ETH Zuerich) Graham Freifeld (Edinburgh), Andreas Galanis (Oxford), Heng Guo (Edinburgh), Mark Jerrum (Queen Mary), Guoliang Qiu (Shanghai Jiao Tong), Chunyang Wang (Nanjing) and Yitong Yin (Nanjing).

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only

Please contact Nidhi Rathi for the password.