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

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

Hi,

Reminding that today's LFCS seminar will start shortly:

  Tuesday, 21 Oct, 4.10pm

  Xinyuan Zhang, Nanjing University

  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:

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

Xinyuan Zhang, Nanjing University

https://sites.google.com/view/xinyuanzhang

  Tue, 21 Oct, 4.10pm

  Venue: IF G.03

Title: Sampling and Counting via Coupling Independence

Abstract

In recent years, the framework of spectral independence has become a

powerful tool for designing efficient algorithms for sampling and

counting problems. In this talk, I will introduce a closely related

concept, called coupling independence, and demonstrate its

applications to both approximate sampling and counting. In

particular, we establish a near-linear time sampler for the

ferromagnetic Ising model with an external field. Furthermore, we

present a deterministic approximate counting algorithm for the

partition functions of spin systems based on coupling independence.

This leads to the first deterministic algorithm that approximately

counts graph colorings in the same regime previously accessible only

to randomized algorithms. Based on joint works with Xiaoyu Chen,

Weiming Feng, Heng Guo, and Zongrui Zou.

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

Upcoming seminars:

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

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.