Midlands Graduate School in the Foundations of Computing Science

Christmas Seminars

Wednesday 18.12.2019, 14.00-17.15
The Diamond, Lecture Theatre 2
University of Sheffield



Programme

14:00-15:00    A categorical perspective on regular cost functions
     Daniela Petrisan (Paris 7)

Regular cost functions are a quantitative extension of regular languages having a very rich theory. Just as regular languages can be expressed as languages accepted by an automaton, or recognized by a finite monoid, or definable in MSO, or, via regular expressions, the theory of cost functions equally comes with quantitative extensions of the above models, introduced in a series of papers of Colcombet. Furthermore these models were shown equi-expressive.

The algebraic structures used for recognition of cost functions are called stabilization monoids, but their definition involves an operation defined only on the idempotent elements. The aim of this talk is to introduce a notion of cost monoid, closely related to that of stabilization monoid, and to show that cost monoids can be seen as Eilenberg-Moore algebras for the monoid monad on a suitably defined category.

This is joint work with Thomas Colcombet and Olivier Stietel.


15:00-15:45    Refreshments

15:45-16:30   Higher categorical structure in HoTT
     Christian Sattler (Nottingham)

I will give an introduction to working with higher categorical structure in homotopy type theory.The approach used is known as complete Segal types, based on the direct part of the simplex category.

Topics discussed follow audience interest, but could include two ways of defining the higher category of types. One is based on the nerve of the 1-category of types, but uses fibrant replacement. The other is based on the left fibration classifier, but is not locally small.


16:30-17:15   Recent advances on the parameterized complexity of integer linear programming
     Sebastian Ordyniak (Sheffield)

Integer Linear Programming (ILP) is probably the archetypical NP-complete optimisation problem, allowing for the efficient solution of many otherwise intractable optimisation problems in computer science by a translation to ILP. Surprisingly, until very recently, only few tractable classes of ILP had been identified, i.e., ILP is known to be solvable in polynomial-time if the constraint matrix is totally uni-modular (Papadimitriou, Steiglitz 1982) and if the number of variables (or constraints) is constant (Lenstra, 1983). In particular, in contrast to SAT and CSP, ILP had not been studied w.r.t. structural restrictions on the constraint matrix.

The aim of this talk is to survey recent results on the (parameterized) complexity of ILP under structural restrictions on the constraint matrix. Namely, we consider structural restrictions on two graphical models of the constraint matrix (that have had a huge impact for our understanding of SAT and CSP): (1) the primal graph having a vertex for every variable and an edge between every two variables occurring together in a constraint and (2) the incidence graph having a vertex for every variable and every constraint and an edge between a variable and a constraint if the variable occurs (with a non-zero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. well-known decompositional parameters such as treedepth, treewidth, and clique-width, we will show that the well known block-structured ILPs (e.g., n-fold, two-stage stochastic, 4-block N-fold, and tree-fold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph.


from 17:30   Pub and Restaurant (Aagrah on Leopold Square has been booked for 18:00)

Organisation

Please contact Georg Struth for all enquiries.

Travel

The seminars will take place at

Lecture Theatre 2
The Diamond
32 Leavygreave Rd
Sheffield S3 7RD
United Kingdom
The Diamond building is within walking distance from Sheffield train station (ca 20min). Lecture theatre 2 is at basement level; it can be found at this floor plan. Please note that for ecological reasons the University of Sheffield no longer issues parking permits for visitors. Please use the following links to find