Events and news relevant to the Laboratory for Foundations of Computer Science

[Ohad Kammar <ohad.kammar@ed.ac.uk>]

Hi,

We'll have an LFCS seminar next week:

  Tuesday, 07 Oct, 4.10pm

  Zongchen Chen, Georgia Institute of Technology (Georgia Tech)

  The seminar will take place in-person only.

We're synchronising the seminar time with the teaching timetable, and

plan to start the talk at the advertised time, so please arrive a minute or two

earlier.

In detail:

----------------------------------------------------------------------

Zongchen Chen, Georgia Institute of Technology (Georgia Tech)

https://sites.gatech.edu/zongchenchen/

  Tue, 07 Oct, 4.10pm

  Venue: IF G.03

Title: New Rapid Mixing Results for the Hardcore Model

Abstract

Over the past decades, a fascinating computational phase transition

has been identified in sampling weighted independent sets from the

hardcore model. However, the computational complexity at the

critical point remains poorly understood, as previous algorithmic

and hardness results all required a constant slack from this

threshold. In this talk, I will introduce our recent result on

resolving this open question at the critical threshold, thus

completing the picture of the computational phase transition.

Specifically, we show that for the critical hardcore model, the mixing

time of Glauber dynamics is always polynomial and in the worst case

super-linear in the number of vertices. Furthermore, we establish

that on random regular graphs, rapid mixing holds far beyond the

uniqueness threshold, showing that the worst-case and average-case

complexities of sampling from the hardcore model are fundamentally

different. Based on joint work with Xiaoyu Chen, Zejia Chen, Tianhui

Jiang, Yitong Yin, and Xinyuan Zhang.

----------------------------------------------------------------------

Upcoming seminars:

------------------

14 Oct: Bruno Cavalar, University of Oxford

21 Oct: Xinyuan Zhang, Nanjing University

28 Oct: Patrick Totzke, University of Liverpool: Optimally Controlling a Random

        Population

If you would like to propose a speaker, or speak yourself, please contact me.

The seminar webpages:

http://web.inf.ed.ac.uk/lfcs/events/lfcs-seminars

Yours,

Ohad.

The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.