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

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

Hi,

We'll have the first of two LFCS seminars today. Note last-week's change from previously 

advertised date:

1. Updated: Monday, 27 Oct, 4.10pm

  Note unusual day.

  Patrick Totzke, University of Liverpool

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:

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

Patrick Totzke, University of Liverpool

https://cgi.csc.liv.ac.uk/~patrick/

  UPDATED: Mon, 27 Oct, 4.10pm

  Note unusual day.

  Venue: UPDATED: Dugald Stewart Building room 1.20

Title: Optimally Controlling a Random Population

Abstract

We will quickly find a park and randomly walk around. I will show you

some butterflies and sheep and tell you how to get them all home safely,

for sure.

The population control problem is a parameterized control problem

where a whole population of agents has to be moved into a target state. The

decision problem asks whether this can be achieved for a finite but

arbitrarily large population. We focus on the random version of this

problem, where every agent is a copy of the same finite MDP and

non-determinism on the global action chosen by the controller is

resolved independently and uniformly at random. Controller seeks to

almost-surely gather the agents in the target states. We show that the

random population control problem is EXPTIME-complete.

Based on joint and unpublished work with Hugo Gimbert and Corto Mascle,

preprint on the arXiv: https://arxiv.org/abs/2411.15181, and code

on

GitHub: https://github.com/SynthesisLab/shepherd.

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

Upcoming seminars:

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

29 Oct: Daniel Spielman, Yale University: Algorithmic Discrepancy Theory

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.