Seminars from 2021/22

ACiD Seminars 2021/22: For now these are on Zoom. Please email [email protected] for information on joining.

Tues 12th October 2021 13:00 online	ACiD Meeting!
Tues 19th October 2021 13:00 online	Tim Boykett (Time’s Up, Linz, Johannes Kepler University, Linz, University of Applied Arts, Vienna) Combinatorics, algebra and reversible computation Reversible computation is a wide field, investigating the ways in which computations that allow the input to be derived from the output can be used, built and studied. Applications lie in quantum computation and extremely low energy computer systems. We are studying collection of reversible gates, in some sense the building blocks of reversible computation. Tom Toffoli did foundational work in 1980, with the Toffoli gate on a binary alphabet named in his honour. If our signal alphabet is A, then n-ary gates are bijections of A^n. Using only the combination by serial and parallel composition and arbitrary wire permutations, we arrive at closed sets of gates studied in the literature variously as permutation clones, reversible Toffoli algebras (RTAs) or memoryless computation. A dual theory based upon monoid weights has been developed by Emil Jebarek (2018). Various authors have shown that odd order alphabets have a finite generating set, this is not the case for even ordered alphabets. We have determined the maximal RTAs, shown that RTAs form an algebraic lattice and several other results. If we include the use of borrowed or ancilla “bits”, we obtain a stronger form of closure. Aaronson, Grier and Schaeffer (2015) have determined all ancilla closed RTAs on a binary alphabet. We are in the process of determining the maximal and minimal ancilla and borrow closed RTAs, drawing on results and techniques from permutation group theory and clone theory. In this talk I will describe the tools we use, the duality results and some of the ongoing work.
Tues 26th October 2021 13:00 online	Eduard Eiben (Royal Holloway) Removing Connected Obstacles in the Plane Is FPT Given two points in the plane, a set of obstacles defined by closed curves, and an integer k, does there exist a path between the two designated points intersecting at most k of the obstacles? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory, wireless computing, and motion planning. It remains NP-hard even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). In this talk, we show that the problem is fixed-parameter tractable (FPT) parameterized by k, by giving an algorithm with running time $k^{O(k^3)}n^{O(1)}$. Here n is the number connected areas in the plane drawing of all the obstacles.
Tues 2nd November 2021 13:00 online	Prudence Wong (University of Liverpool) Greedy is Optimal for Online Restricted Assignment for Unit Size Jobs We study online scheduling of unit-sized jobs in restricted assignment problem. We show that the greedy algorithm is an optimal online algorithm. Typically, an online algorithm is proved to be an optimal online algorithm through bounding its competitive ratio and showing a lower bound with matching competitive ratio. However, our analysis does not take this approach. Instead, we prove the optimality without giving the exact bounds on competitive ratio. Roughly speaking, given any online algorithm and a job instance, we show the existence of another job instance for greedy such that (i) the two instances admit the same optimal offline schedule; (ii) the cost of the online algorithm is at least that of the greedy algorithm on the respective job instance. With these properties, we can show that the competitive ratio of the greedy algorithm is the smallest possible.
Tues 9th November 2021 13:00 online	Karolina Okrasa (Warsaw University of Technology) The (list) homomorphism problem in hereditary graph classes Let G and H be graphs. We say that f: V(G) -> V(H) is a homomorphism from G to H if for every edge uv of G, f(u)f(v) is an edge of H. For a fixed H, we study the computational problem of deciding whether there exists a homomorphism from a given G to H. We also focus on the list homomorphism problem, where each vertex v of the instance G is equipped with some list of vertices from H, and we ask for a homomorphism that maps every vertex of G to some element from its list. For a fixed H, we denote by Hom(H) the computational problem of deciding whether there exists a homomorphism from a given G to H, and by LHom(H) the corresponding list variant of the problem. Homomorphisms can be viewed as a generalization of colorings: note that the Hom(K_k) problem is equivalent to the k-Coloring problem. Since the problems of coloring graphs excluding a fixed induced subgraph F receive a significant amount of attention amongst researchers, it is natural to ask how these results generalize to graph homomorphisms. We examine for which pairs (F, H) of graphs, the Hom(H) problem can be solved in polynomial/subexponential time in F-free graphs. The cases when F is isomorphic to some subdivided K_{1,3} are particularly interesting: while assuming the ETH, we can exclude the existence of subexponential time algorithms for k-Coloring these graphs, the classification for homomorphisms seems to be much more involved. This is joint work with Paweł Rzążewski.
Tues 16th November 2021 13:00 online	Torsten Mütze (University of Warwick) Efficient generation of elimination trees and Hamilton paths on graph associahedra An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they are closely related to centered colorings and tree-depth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm (see http://www.combos.org/elim). This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time O(m+n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time O(1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal. This is joint work with Jean Cardinal (ULB) and Arturo Merino (TU Berlin).
Tues 23rd November 2021 13:00 online	Paloma Lima (Bergen) On the parameterized complexity of b-Coloring A b-coloring of a graph G with k colors is a partition of the vertices of G into k independent sets such that each of them contains a vertex that has a neighbor in all of the remaining ones. This notion was initially introduced by Irving and Manlove in 1999 to describe the worst case behaviour of a color-suppressing heuristic for the graph coloring problem. The corresponding computational problem takes as input a graph G and an integer k and asks if G has a b-coloring with k colors. In this talk, I will survey some recent results on the b-coloring problem from the point of view of parameterized complexity and talk about related open problems.
Tues 30th November 2021 13:00 online	Carla Groenland (University of Utrecht) Tight bounds for counting colourings parameterised by cutwidth via matrix ranks We consider the fine-grained complexity of counting the number of list q-colourings modulo a prime p. We show that if p divides q-1, the ‘best’ running time is (q-1)^{ctw} poly(n), where n is the number of vertices of the input graph and ctw the cutwidth, and if p does not divide q-1, the ‘best’ running time is q^{ctw} poly(n) (where ‘best’ means we have an algorithm which is tight under SETH). Interestingly, this dependence on (p,q) can be described via the rank of a certain ‘compatibility matrix’ over F_p. This is based on joint work with Isja Mannens, Jesper Nederlof and Krisztina Szilágyi.
Tues 7th December 2021 13:00 online	Tyler Helmuth (Durham Maths) Approximate Counting and Sampling at Low Temperatures There is a rich interplay between computer science and physics, going back (at least) as far as the invention of Markov chain Monte Carlo for computing thermodynamic properties of a gas composed of hard spheres. For a discrete version of the hard sphere gas called the independent set model, celebrated results of Sly and Weitz show that the link between the subjects is deep: there is a precise relation between the feasibility of approximate counting and the existence of a physical phase transition. In particular, there is no general-purpose approximate counting algorithm for the independent set model in the ‘low temperature’ phase of the model. I will introduce these problems and explain that all is not lost: in many circumstances, approximate counting algorithms do exist at low temperatures. These algorithms are based on techniques from mathematical physics and implement physical intuitions about the low temperature phase.
Tues 11th January 2022 13:00 online	Caterina Viola (University of Oxford) The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over infinite-domains. This extends a result of Brakensiek and Guruswami [SODA’20] for promise (non-valued) CSPs (on finite domains). Joint work with Stanislav Živný.
Tues 18th January 2022 13:00 online	Dömötör Pálvölgyi (Eötvös Loránd University) At most 3.55^n stable matchings We improve the upper bound for the maximum possible number of stable matchings among n jobs and n applicants (formerly known as n men and n women) from 131072^n+O(1) to 3.55^n+O(1). To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects. Joint work with Cory Palmer.
Tues 25th January 2022 13:00 online	Robert Johnson (Queen Mary) Correlation for Permutations A family F of subsets of {1,2,..,n} is an up-set if every superset of a member of F is also a member of F. The well-known (and very useful) Harris-Kleitman inequality says that any two up-sets are positively correlated. Our aim in this talk is to explore analogues of the Harris-Kleitman inequality for families of permutations. It turns out that there are two natural notions of what it means for a family of permutations to be an up-set (corresponding to the strong and weak Bruhat orders) and surprisingly the correlation that occurs in the two cases is quite different. This is joint work with Imre Leader and Eoin Long.
Tues 1st February 2022 13:00 online	Candida Bowtell (University of Oxford) The n-queens problem How many ways are there to place n queens on an n by n chessboard so that no two can attack one another? What if the chessboard is embedded on the torus? Let Q(n) be the number of ways on the standard chessboard and T(n) the number on the toroidal board. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne^{-3})^n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne^{-3})^n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n). In this talk we’ll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost’ configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption. This is joint work with Peter Keevash.
Tues 8th February 2022 13:00 online	Viresh Patel (University of Amsterdam) Computational counting and zeros of graph polynomials In recent decades there has been a lot of interest in efficient algorithms to (approximately) count objects such as independent sets or proper k-colourings in graphs. More generally, these counting problems have associated generating polynomials (the independence polynomial for independent sets and the chromatic polynomial for proper k-colourings), and one is also interested in efficient approximation algorithms to evaluate these polynomials at different points. I will give an overview of a relatively recent technique called Taylor polynomial interpolation for designing these counting algorithms. We will see an intimate (but not fully understood) connection between computational complexity of counting problems and the locations of zeros of the associated counting polynomials.
Tues 15th February 2022 13:00 online	ACiD Meeting!
Tues 22nd February 2022 13:00 online
Tues 1st March 2022 13:00 MCS 2068 and online	Marc Roth (University of Oxford) The Parameterized Complexity of Pattern Counting Problems In this talk, I will present recent results on the complexity of pattern counting problems from the perspective of parameterized and fine-grained complexity theory. In the first part, I will introduce and discuss “Complexity Monotonicity”, a novel and powerful tool due to Curticapean, Dell and Marx (STOC 2017), which provides a unifying view on problems that require to count small structures in large networks. In the second part I will give an overview over recent complexity classifications for counting subgraphs and induced subgraphs that have been obtained by establishing connections between Complexity Monotonicity and the structure of simplicial graph complexes and Cayley graph expanders. Based on joint works with Julian Dörfler, Jacob Focke, Norbert Peyerimhoff, Johannes Schmitt, Jakob Stix, Alina Vdovina, and Philip Wellnitz.
Tues 8th March 2022 13:00 online	Max Gadouleau (Durham) Linear programming complementation In this talk, we introduce a new kind of duality for Linear Programming (LP), that we call LP complementation. We prove that the optimal values of an LP and of its complement are complement pairs (provided that either the original LP or its complement has an optimal value greater than one). The main consequence of the LP complementation theorem is for hypergraphs. We introduce the complement of a hypergraph and we show that the fractional packing numbers of a hypergraph and of its complement are complement pairs; similar results hold for fractional matching, covering and transversal numbers. This hypergraph complementation theorem has several consequences for fractional graph theory. In particular, we relate the fractional dominating number of a graph to the fractional total dominating number of its complement.
Tues 15th March 2022 13:00 online	Jan Goedgebeur (KU Leuven) An introduction to computational graph theory and generation algorithms Computers are often used in combinatorics to determine if combinatorial objects with given structural or extremal properties exist as these existence problems are often too complex to solve by hand. This is done by designing and implementing generation algorithms which construct combinatorial objects from a given class (typically avoiding the generation of isomorphic copies) and analysing the resulting graphs. In this talk we will give an introduction to computational graph theory and the design of generation algorithms in particular. We will also give concrete examples of how these generation algorithms have helped to gain new insights and solve problems in mathematics and in chemistry.