Seminars
Seminars from previous years: 2024/25 2023/24 2022/23 2021/22 2020/21 2019/20 2018/19 2017/18 2016/17 2015/16 2014/15 2013/14 2012/13 2011/12 2010/11
ACiD Seminars 2025/26.
| Tues 7th October 2025 13:00 MCS 3052 and online | Petar Markovic and Dmitriy Zhuk The Great CSP Swindle! |
| Tues 14th October 2025 13:00 MCS 3052 and online | ACiD Meeting! |
| Tues 21st October 2025 13:00 MCS 3052 and online | Bruno Cavalar (Oxford) Monotone circuit complexity of matching We show that the perfect matching function on $n$-vertex graphs requires monotone circuits of size $2^{n^{\Omega(1)}}$. This improves on the $n^{\Omega(\log n)}$ lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings. |
| Tues 28th October 2025 13:00 MCS 3052 and online | David Manlove (Glasgow) Course Allocation with Credits via Stable Matching In the Course Allocation problem, there are a set of students and a set of courses at a given university. University courses may have different numbers of credits, typically related to different numbers of learning hours, and there may be other constraints such as courses running concurrently. Our goal is to allocate the students to the courses such that the resulting matching is stable, which means that no student and course(s) have an incentive to break away from the matching and become assigned to one another. We study several definitions of stability and for each we give a mixture of polynomial-time algorithms and hardness results for problems involving verifying the stability of a matching, finding a stable matching or determining that none exists, and finding a maximum size stable matching. We also study variants of the problem with master lists of students, and lower quotas on the number of students allocated to a course, establishing additional complexity results in these settings. This work was motivated by the allocation of Honours students to courses within the School of Law at UoG, and I will discuss our experience with this application. This is joint work with Mathijs Barkel, Fraser Paterson and Pepe Rodríguez, and a related paper appeared at SAGT 2025 (see here for the full paper) |
| Tues 4th November 2025 13:00 MCS 3052 and online | Tala Eagling-Vose (Durham) Colouring and the Forbidden “H” Graph It is known that 3-Colouring is NP-complete for H-subgraph-free graphs whenever H contains a cycle, a vertex of degree at least 5, or a component with two vertices of degree 4. On the other hand, Colouring is polynomial-time solvable for H-subgraph-free graphs when H is a forest of maximum degree at most 3 in which each component has at most one vertex of degree 3. For connected graphs H, this leaves two unresolved cases: when H is a tree of maximum degree 4 with exactly one vertex of degree 4, or a tree of maximum degree 3 with at least two vertices of degree 3. We focus on the so-called subdivided “H” graphs, where H is either: (i) a subdivided H_0: a tree of maximum degree 4 with exactly one vertex of degree 4 and no vertices of degree 3, or (ii) a subdivided H_1: a tree of maximum degree 3 with exactly two vertices of degree 3. We present new polynomial-time techniques that allow us to determine the complexity of Colouring on H-subgraph-free graphs for all remaining subdivided “H” graphs, thereby completing the classification for both cases (i) and (ii). |
| Tues 11th November 2025 13:00 MCS 3052 and online | Barnaby Martin (Durham) Complexity Classification Transfer for CSPs via Algebraic Products We study the complexity of infinite-domain constraint satisfaction problems: our basic setting is that a complexity classification for the CSPs of first-order expansions of a structure A can be transferred to a classification of the CSPs of first-order expansions of another structure B. We exploit a product of structures (the algebraic product) that corresponds to the product of the respective polymorphism clones and present a complete complexity classification of the CSPs for first-order expansions of the n-fold algebraic power of (Q;<). This is proved by various algebraic and logical methods in combination with knowledge of the polymorphisms of the tractable first-order expansions of (Q;<) and explicit descriptions of the expressible relations in terms of syntactically restricted first-order formulas. By combining our classification result with general classification transfer techniques, we obtain surprisingly strong new classification results for highly relevant formalisms such as Allen’s Interval Algebra, the n-dimensional Block Algebra, and the Cardinal Direction Calculus, even if higher-arity relations are allowed. Our results confirm the infinite-domain tractability conjecture for classes of structures that have been difficult to analyse with older methods. For the special case of structures with binary signatures, the results can be substantially strengthened and tightly connected to Ord-Horn formulas; this solves several longstanding open problems from the AI literature. |
| Tues 18th November 2025 13:00 online only | Sophie Spirkl (Waterloo) Colouring tournaments Tournaments (orientations of complete graphs) are a fun counterpart to the induced subgraphs world, and we can ask all sorts of analogous questions: When can we colour in polynomial time? What if we exclude some induced subtournament? What causes large chromatic number? I don’t have all the answers, but I will tell you some things about this. |
| Tues 25th November 2025 13:00 MCS 3052 and online | Danny Vagnozzi (Durham) Approximating 1-in-3 SAT: NP-hard… or what? Given a satisfiable instance of 1-in-3 SAT, it is NP-hard to find a satisfying assignment for it, but it may be possible to efficiently find a solution subject to a weaker (not necessarily Boolean) predicate than `1-in-3′. There is a folklore conjecture predicting which choices of weaker predicates lead to tractability and for which the task remains NP-hard. One specific predicate, corresponding to the problem of linearly ordered 3-colouring of 3-uniform hypergraphs, has been mentioned in several recent papers as an obstacle to further progress in proving this conjecture. We prove that the problem for this predicate is NP-hard, as predicted by the conjecture. We use the Promise CSP framework, where the complexity analysis is performed via the algebraic approach, by studying the structure of polymorphisms, which are multidimensional invariants of the problem at hand. The analysis of polymorphisms is in general a highly non-trivial task, and topological combinatorics was recently discovered to provide a useful tool for this. There are two distinct ways in which it was used: one is based on variations of the Borsuk-Ulam theorem, and the other aims to classify polymorphisms up to certain reconfigurations (homotopy). Our proof, whilst combinatorial in nature, shows that our problem is the first example where the features behind the two uses of topology appear together. Thus, it is likely to be useful in guiding further development of the topological method aimed at classifying Promise CSPs. An easy consequence of our result is the hardness of another specific Promise CSP, which was recently proved by Filakovský et al. by employing a deep topological analysis of polymorphisms. |
| Tues 2nd December 2025 13:00 MCS 3052 and online | Karolina Okrasa (Oxford) TBA |
| Tues 9th December 2025 13:00 MCS 3052 and online | George Osipov (Oxford) Parameterized Deletion in Graphs and CSPs Many classical problems on graphs can be phrased as deletion problems, for example: – Vertex Cover asks to delete k vertices from a graph so that it becomes edgeless, – Odd Cycle Transversal asks to delete k vertices from a graph so that it becomes bipartite, – Directed Feedback Arc Set asks to delete k arcs from a digraph so that it becomes acyclic, – Multicut asks to delete k edges from a graph so that no terminal pair remains connected. These problems are NP-hard but become fixed-parameter tractable when parameterized by the solution cost k, and their study has been instrumental in the development of parameterized algorithms. All these problems (and many more) have equivalent formulations as MinCSP(Γ): given an instance of the constraint satisfaction problem over Γ, delete k constraints so that it becomes satisfiable. A major goal in the area is to classify the parameterized complexity of MinCSP(Γ) for each constraint language Γ. In this talk, I will discuss the main results in this direction, and showcase some of the existing tools by classifying the complexity of binary temporal MinCSPs (based on joint work with Marcin Pilipczuk and Magnus Wahlström, ESA’24). |
| Tues 13th January 2026 13:00 MCS 3052 and online | Sergey Kitaev (Strathclyde) Human-verifiable proofs in the theory of word-representable graphs A graph is word-representable if it can be represented in a certain way using alternation of letters in words. Word-representable graphs generalize several important and well-studied classes of graphs, and they can be characterized by semi-transitive orientations. Recognizing word-representability is an NP-complete problem, and the bottleneck of the theory of word-representable graphs is convincing someone that a graph is non-word-representable. In the literature, a variety of (usually ad hoc) proofs of non-word-representability for graphs, or families of graphs, appear, but for a randomly selected graph, one should expect looking at O(2^{#edges}) orientations and justifying that none of them is semi-transitive. Even if a computer would print out all these orientations and would point out what is wrong with each of the orientations, such a proof would be essentially non-checkable by a human. In this talk, I will discuss recently developed methods for an automatic search of human-verifiable proofs of graph non-word-representability. In particular, the new tools give “short” proofs of non-word-representability, generated automatically by publicly available user-friendly software, of the Shrikhande graph on 16 vertices and 48 edges (6 “lines” of proof) and the Clebsch graph on 16 vertices and 40 edges (10 “lines” of proof). Producing such short proofs for relatively large graphs would not be possible without the instrumental tool introduced recently (allowing to assume orientations of several edges in a graph, not just one edge as it was previously used) that is a game changer in the area. This is joint work with Haoran Sun. |
| Tues 20th January 2026 13:00 MCS 3052 and online | |
| Tues 27th January 2026 13:00 MCS 3052 and online | |
| Tues 4th February 2026 13:00 MCS 3052 and online | |
| Tues 11th February 2026 13:00 MCS 3052 and online | |
| Tues 18th February 2026 13:00 MCS 3052 and online | |
| Tues 25th February 2026 13:00 MCS 3052 and online | |
| Tues 3rd March 2026 13:00 MCS 3052 and online | |
| Tues 10th March 2026 13:00 MCS 3052 and online | |
| Tues 17th March 2026 13:00 MCS 3052 and online |