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

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

Hi,

We'll have **two** LFCS seminars next week. There are changes from previously 
announced
plans, so please read more carefully:

1. Updated: Monday, 27 Oct, 4.10pm
  Note unusual day.
  Patrick Totzke, University of Liverpool

2. Wednesday, 29 Oct, 11.10am
  Note unusual day and time.
  Daniel Spielman, Yale University

  Daniel is this year's Milner Lecturer and will kindly give this additional 
seminar on
  Wednesday intended for more specialised audience.

Both seminars 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
  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.

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

Daniel Spielman, Yale University
http://cs-www.cs.yale.edu/homes/spielman/

  Wed, 29 Oct, 11.10pm
  Venue: Appleton Tower Lecture Theatre 1

Title: Algorithmic Discrepancy Theory

Abstract

We survey algorithms that have been used to effectively realize the
promises of discrepancy theory, including Beck and Fiala's technique
for minimizing Euclidean discrepancy, algorithmic versions of
Spencer's theorem, and the Gram-Schmidt Walk of Bansal, Dadush, Garg, and
Lovett. We will finish with some conjectures and open problems.

Bio:

Dan Spielman is the Sterling Professor of Computer Science, and
Professor of Mathematics and Statistics, at Yale University.
Spielman's wide-ranging research spans the design and analysis of
algorithms, spectral graph theory, numerical linear algebra, coding
theory, linear programming, statistics and data science. He has
received numerous awards for groundbreaking contributions in many of
these areas, including the Goedel Prize (twice, both in 2008 and 2015),
the Fulkerson Prize (2009), the Nevanlinna Prize (2010), the Polya
Prize (2014), the Held Prize (2021), and the Breakthrough Prize in
Mathematics (2023).

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

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.