FOX group holds weekly theory seminar (usually on Wednesday afternoon). If you are interested in giving a talk in our group, please contact Sagnik Mukhopadhyay or Max Sandström. The talks are usually recorded and can be found here. The talks are 45 minutes long with 10-15 minutes time for questions and discussion.
In the spring of 2024 the seminar is held in Broad Lane block LT5 at 3 – 4pm. The easiest way to get to the lecture theatre is by entering the Frederick Mappin building from the main entrance (on Mappin Street), climbing the stairs one floor to Floor E, and turning to the left, following the outer edge of the building. Keep an eye out for the signs labelled Broad Lane building and then Lecture Theatre 1-5, and you will not get lost.
Upcoming talks
8 May 2024 | Fahad Panolan | Fixed Parameter Semi-streaming Algorithms |
We explore semi-streaming algorithms for parameterized graph problems and present a systematic study of this topic. We devise meta-theorems specifically designed for parameterized streaming and demonstrate their applicability by obtaining poly(k) · n · polylog(n)-space streaming algorithms for well-studied problems such as Feedback Vertex Set on Tournaments, Cluster Vertex Deletion, Proper Interval Vertex Deletion and Block Vertex Deletion. In the process, there is a fundamental connection between semi-streaming algorithms for recognizing graphs in a graph class H and semi-streaming algorithms for the problem of vertex deletion into H. We also present an algorithmic machinery for obtaining poly(k) · n · polylog(n)-space streaming algorithms for cut problems like Graph Bipartitization, Multiway Cut and Subset Feedback Vertex Set. This is a joint work with Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan, Saket Saurabh, and Meirav Zehavi. |
29 May 2024 | Prof. Georg Struth | Dedekind Quantaloids and their Intuitionistic Modal Algebras |
I will discuss the modal algebra on Dedekind quantaloids, but restrict my attention mainly to Dedekind quantales for the sake of simplicity. Dedekind quantales are involutive quantales satisfying a modular or Dedekind law. The modal box and diamond operators on these structures are induced by domain and codomain operators, which are defined as for algebras of binary relations. But by contrast to those algebras, the subalgebras of Dedekind quantales, on which the modal operators act, form complete Heyting algebras. The modal algebra on Dedekind quantales, in the style of Jónsson and Tarski’s boolean algebras with operators, is therefore intuitionistic. I will relate it with intuitionistic dynamic logics and Hoare logics that might be of interest in computer science. With few exceptions, all results in this paper have been verified with the Isabelle/HOL proof assistant. This is joint work with Philippe Malbos (ICJ Lyon) and Damien Pous (ENS Lyon). |
Past talks
2 May 2024 | Rajesh Chitnis (University of Birmingham) | Lower Bounds for Exact & Approximate k-Disjoint-(Shortest)-Paths |
1 May 2024 | Giulio Guerrieri (University of Sussex) | Solvability, Scrutability and Lambda Calculus |
24 April 2024 | Prof. Parinya Chalermsook (Aalto University) | Fast and Survivable Network Design |
17 April 2024 | Tanguy Massacrier | Single-set cubical categories and their formalisation with a proof assistant |
6 March 2024 | Charles Grellois | Semantic Approaches to Verification of Functional Programs |
31 January 2024 | Floris Geerts (University of Antwerp) | The Expressive Power of Graph Learning |
16 January 2024 | Emmanoulis Vasilakis | Structural Parameterizations and the Price of Generality |
6 December 2023 | Navid Talebanfard | Circuits and Algorithms, Recent Developments |
22 November 2023 | Chhaya Dhingra (University of Bristol) | (1 + \epsilon)-Approximate Shortest Paths in Dynamic (with Edges Insertions and Deletions) Streaming Model |
15 November 2023 | Andreas Feldmann | An Efficient Parameterized Approximation Scheme for Steiner Forest in Low Treewidth Graphs |
8 November 2023 | Ruben Turkenburg (Radboud University) | Preserving and Reflecting Notions of Equivalence |
18 October 2023 | Maksim Zhukovskii | Triangle Bootstrap Percolation |
11 October 2023 | Mike Cruchten | An Introduction to Lasso Automata |
4 October 2023 | Christian Konrad (University of Bristol) | Lower Bounds for Two-Pass Streaming Algorithms for Maximum Matching |
20 September 2023 | Ilay Hoshen (Tel-Aviv University) | Simonovits’s Theorem in Random Graphs |
28 June 2023 | Prof. Parinya Chalermsook (Aalto University) | Algorithms and Data Structures via Extremal Combinatorics, and Back |
7 June 2023 | Maksim Zhukovskii | First Order Complexity of Random Structures |
31 May 2023 | Prof. Heribert Vollmer (Leibniz University Hannover) | Enumeration Classes Defined by Circuits |
30 May 2023 | Chelsea Edmonds (University of Cambridge) | The Locale-Centric Approach for Formalising Large Mathematical Hierarchies |
24 May 2023 | Sayan Bhattacharya (University of Warwick) | Recent Advances in Dynamic Matching |
10 May 2023 | Harsh Beohar | Hennessy-Milner theorems for coalgebras |
27 April 2023 | Prof. Andrew Pitts (University of Cambridge) | Locally nameless sets |
12 April 2023 | Prof. Juha Kontinen University of Helsinki | An Introduction to Team Semantics |
22 March 2023 | Max Sandström | Linear Temporal Logic under Team Semantics |