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:

  1. Monday, 14 Sep, 4.10pm (unusual day)

  Danel Ahman, University of Tartu

2. Tuesday, 15 Sep, 4.10pm (usual day)

  Pranshu Gaba, Tata Institute of Fundamental Research, Mumbai

  The 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:

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

Danel Ahman, University of Tartu

https://danel.ahman.ee

  Mon, 14 Sep, 4.10pm

  Venue: AT 2.14 (note unusual place and day)

Title: A deeper dive into combining graded monads and graded modal types for temporal resource management

Abstract

In this talk, I will take a deeper dive into the calculus for combining

generally graded monads and generally graded modal types for

specifying, controlling, and verifying temporal properties of

programs' resources which I also talked about at the Plotkin 80

symposium. To recall, by such resources we mean ones whose usage is

time-sensitive and/or time-critical, and which, while perhaps

already physically available to a program, can be used or acted upon

only after a certain amount of time has passed or some prescribed

external events have taken place (perhaps in some order, perhaps not).

In the talk, I will discuss some of the design choices underlying the

calculus, and explore in more depth both its stateful temporally aware

operational semantics and its presheaves-based denotational

semantics, including their relationship. I will also discuss some

extensions to the calculus for modelling more realistic programming

scenarios.

(This talk is based on past and ongoing joint work with Andres Alumets,

Mariana Milicich, Gašper Žajdela, and Joosep Tavits.)

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

Pranshu Gaba, Tata Institute of Fundamental Research, Mumbai

https://pranshugaba.com/

  Tue, 15 Sep, 4.10pm

  Venue: Dugald Steward Building DS-1.20 (unusual venue)

Title: Sure-Almost-Sure Window Mean Payoff in Markov Decision Processes

Abstract

Given rationals α and β, the sure-almost-sure problem for a

quantitative objective φ in a Markov decision process (MDP) asks if one

can simultaneously ensure that all outcomes of the MDP have φ-value at

least α (i.e., sure α satisfaction), and with probability 1 the outcome

has φ-value at least β (i.e., almost-sure β satisfaction). Moreover,

if simultaneous satisfaction of objectives is possible, then one

would also like to construct a strategy that achieves this. Even if both

sure satisfaction and almost-sure satisfaction for an objective are

known, combining the two is often non-trivial and requires novel

techniques and approaches.

In this talk, we look at the sure-almost-sure problem for window

mean-payoff objectives. The window mean-payoff objective

strengthens the standard mean-payoff objective by requiring that the

average payoff from each point in the play become at least than the

threshold in at most ℓ steps. For the window mean-payoff objective, we

show that while the computational complexity of the sure-almost-sure

problem matches that of sure satisfaction and almost-sure

satisfaction, the memory requirement of winning strategies for

sure-almost-sure satisfaction is greater than that of both sure and

almost-sure satisfaction.

Link:

https://arxiv.org/abs/2605.12191

(CONCUR 2026)

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

Upcoming seminars:

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

22 Sep: Sabine Oechsner, Vrije Universiteit Amsterdam

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

It was good to see so many of you at the various symposia this week.

Happy new year everyone,

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.