Below you'll find the programme for the Seminar and PhD Seminar on Combinatorics, Games and Optimisation.
This seminar series covers many of the research areas in the Department: discrete mathematics, algorithms, game theory and operational research.
Unless stated below, this Seminar normally takes place:
Questions, suggestions, etc., about the seminar can be forwarded to Enfale Farooq, the Research Manager, on E.Farooq@lse.ac.uk
IMPORTANT - Due to the ongoing COVID-19 epidemic seminars will now take place online.
Upcoming speakers:
Thursday 28 January - Anthony Bonato (Ryerson University)
2pm on Zoom
The localization game played on graphs
Graph searching investigates combinatorial models for the detection or neutralization of an adversary’s activity on a network. One such model is the \emph{localization game}, where pursuers use distance probes to capture an invisible evader. We present new results on the \emph{localization number} of a graph, which is the minimum number of pursuers needed to capture the evader. We survey what is known and unknown for the localization number, discuss connections with the chromatic number, and give bounds on graph families such as hypercubes, incidence graphs of combinatorial designs, and Kneser graphs.
Friday 29 January - Alp Müyesser (FU Berlin)
12pm on Zoom
Rainbow factors and trees
Generalizing a conjecture of Aharoni, Joos and Kim asked the following intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) be a sequence of m graphs on the common vertex set [n]. What is the weakest minimum degree restriction we can impose on each G_i to guarantee a rainbow copy of H? Joos and Kim answered this question when H is a Hamilton cycle or a perfect matching. We provide an asymptotic answer when H is an F-factor, or a spanning tree with maximum degree o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.
Thursday 4 February - Lap Chi Lau (University of Waterloo)
2pm on Zoom
A spectral approach to network design
We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional non-negative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. We may also discuss other applications of the spectral rounding results, including weighted experimental design and additive spectral sparsification.
Friday 5 February - Sophie Huiberts (Centrum Wiskunde & Informatica)
12pm on Zoom
On the Integrality Gap of Binary Integer Programs with Gaussian Data
Abstract TBC.
Previous seminars in the series:
Thursday 28 January - Anthony Bonato (Ryerson University)
The localization game played on graphs
Graph searching investigates combinatorial models for the detection or neutralization of an adversary’s activity on a network. One such model is the \emph{localization game}, where pursuers use distance probes to capture an invisible evader. We present new results on the \emph{localization number} of a graph, which is the minimum number of pursuers needed to capture the evader. We survey what is known and unknown for the localization number, discuss connections with the chromatic number, and give bounds on graph families such as hypercubes, incidence graphs of combinatorial designs, and Kneser graphs.
Thursday 21 January - Rahul Savani (University of Liverpool)
The Complexity of Gradient Descent
We study search problems that can be solved by performing Gradient Descent on a convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain [0,1]^2 is complete for the intersection of PPAD and PLS. This is the first natural problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more "natural" counterpart to the intersection of PPAD and PLS and contains many interesting problems - is itself equal to the intersection of PPAD and PLS.
Joint work with: John Fearnley, Paul W. Goldberg, and Alexandros Hollender. Preprint available here.
Thursday 10 December - Marthe Bonamy (Université de Bordeaux)
Towards polynomial Chi-boundedness of graphs with no long path
There are graphs of arbitrarily high chromatic number which contain no triangle and in fact no short cycle. However, in some graph classes with enough structure, we can show that the chromatic number of the graphs is bounded by some function of their largest clique -- in other words, that class is chi-bounded. One of the first such results was by Gyarfas in 1987: for any t, the class of Pt-free graphs is chi-bounded. The corresponding function is unfortunately exponential, and it remains a major open problem whether we can replace it with a polynomial. Here, we consider a relaxation of this problem, where we compare the chromatic number with the size of the largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that every Pt-free graph which does not contain Kp,p as a subgraph is p^c-colourable. This is joint work with Nicolas Bousquet, Michal Pilipczuk, Pawel Rzazewski, Stéphan Thomassé and Bartosz Walczak.
Friday 4 December - Edin Husić (LSE)
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
We present a simple auction algorithm that obtains an approximate market equilibrium for the exchange market model with divisible goods where the demands of the agents satisfy the weak gross substitutes (WGS) property. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash Social Welfare problem. This is joint work with Jugal Garg and László Végh.
Thursday 3 December - Luke Postle (University of Waterloo)
Further progress towards Hadwiger's conjecture
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^{6})$-colorable.
Friday 27 November - Domenico Mergoni (LSE)
About the pentagon conjecture
The Pentagon Conjecture states that every cubic graph of sufficiently high girth admits a homomorphism to the cycle of length 5. We exploit the study of this problem to introduce some interesting approaches for this kind of task. We then use the obtained tools to approach some approximations of the Pentagon Problem.
Thursday 26 November - Liana Yepremyan (LSE)
Ryser's conjecture and more
A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order $n\times n$ contains a transversal of order $n-1$. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order $n$ contains a matching of size $(n-4)/3$. The third problem we'd like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems. Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.
Friday 20 November - Chhaya Trehan (LSE)
Constructing Near-Additive Spanners in Dynamic Streams
Graph spanners are a fundamental and well-studied combinatorial construct with numerous applications. They are particularly useful for computing approximately shortest paths, routing schemes and distance oracles. Given a pair of parameters alpha >=1, \beta >= 0, a spanning subgraph H of an unweighted undirected graph G is called an (\alpha, \beta)-spanner of G if for every pair of vertices (u,v), d_H (u,v) <= \alpha . d_G(u,v) + \beta, where d_G(u,v) and d_H(u,v) stand for distances between u and v in G and H respectively. Elkin and Peleg proved the existence and constructibility of sparse spanners for which the multiplicative term \alpha can be arbitrarily close to 1. Such spanners are called near-additive spanners. Near-additive spanners preserve large distances much more faithfully than the more traditional multiplicative spanners. Multiple algorithms have been devised for the efficient construction of near-additive sparse spanners in sequential, distributed and (static) streaming models of computation. In the streaming model of computation, the vertex set of the input graph is known to the algorithm and the edge set is revealed one at a time. In the dynamic streaming or turnstile setting, edges can be added as well as removed as the stream progresses. We present the first dynamic-streaming algorithms for constructing near-additive spanners. Our algorithm outputs a near-additive spanner with the same stretch and size as the state of the art algorithm due to Elkin and Neiman. This is joint work with Michael Elkin of BGU, Israel.
Thursday 19 November - Matoula Kotsialou (LSE)
Incentivising Participation in Liquid Democracy with Breadth-First Delegation
Liquid democracy allows members of an electorate to either directly vote over alternatives, or delegate their voting rights to someone they trust. Most of the liquid democracy literature and implementations allow each voter to nominate only one delegate per election. However, if that delegate abstains, the voting rights assigned to her are left unused. To minimise the number of unused delegations, it has been suggested that each voter should declare a personal ranking over voters she trusts. We show that even if personal rankings over voters are declared, the standard delegation method of liquid democracy remains problematic. More specifically, we show that whenpersonalrankings over voters are declared, it could be undesirable to receive delegated voting rights, which is contrary to what liquid democracy fundamentally relies on. To solve this issue, we propose a new method to delegate voting rights in an election, calledbreadth-first delegation. Additionally, the proposed method prioritises assigning voting rights to individuals closely connected to the voters who delegate.
This is joint work with Luke Riley.
Friday 13 November - Nóra Frankl (LSE)
VC-saturated set systems
A family of sets is d-saturated, if it has VC-dimension d and adding any new set to the family increases the VC-dimension. We study the minimum cardinality of a d-saturated family on a ground set of size n. For d=1 this minimum is n+1, which is the same as the Sauer-Shelah bound for the maximum cardinality of a family of VC-dimension 1. For d>1 we find upper bounds that do not depend on n, only on d.
Joint work with Sergei Kiselev, Andrey Kupavskii and Balázs Patkós.
Thursday 12 November - Johannes Ruf (LSE)
Hedging with linear regressions and neural networks
We study the use of neural networks as nonparametric estimation tools for the hedging of options. To this end, we design a network, named HedgeNet, that directly outputs a hedging strategy given relevant features as input. This network is trained to minimise the hedging error instead of the pricing error. Applied to end-of-day and tick prices of S&P 500 and Euro Stoxx 50 options, the network is able to reduce the mean squared hedging error of the Black-Scholes benchmark significantly.
We illustrate, however, that a similar benefit arises by a simple linear regression model that incorporates the leverage effect. Finally, we argue that outperformance of neural networks previously reported in the literature is most likely due to a lack of data hygiene. In particular, data leakage is sometimes unnecessarily introduced by a faulty training/test data split, possibly along with an additional ‘tagging’ of data.
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3580132
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3486363
(Joint work with Weiguan Wang)
Thursday 5 November - Neil Olver (LSE)
Intersecting multiple matroids via iterative refinement
A classical result by Edmonds says that given two matroids on the same ground set, a set of maximum weight that is independent in both matroids can be found in polynomial time. This is an important generalization of maximum weight bipartite matching. It is also well-known that the problem becomes NP-hard once there are more than two matroids involved.
Here we show how to obtain a factor 2 approximation for three matroids, based on the natural LP relaxation. Previously, a 2+epsilon approximation algorithm was known for any epsilon > 0, using local search methods, and there was no bound better than 3 on the integrality gap of the natural relaxation. Our approach is based on iterative routing, and introduces a new ingredient that we call "iterative refinement"
(Joint work with André Linhares, Chaitanya Swamy and Rico Zenklusen).
Friday 30 October - Amedeo Sgueglia (LSE)
Clique factors in randomly perturbed graphs
We study the model of randomly perturbed dense graphs, which is the union of any n-vertex graph G_α with minimum degree α and the binomial random graph G(n,p). In this talk, we shall examine in detail one of the central question in this area: to determine when G_α ∪ G(n,p) contains clique factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the complete graph K_k. We offer several new sharp and stability results. This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.
Thursday 29 October - Amitabh Basu (Johns Hopkins University)
Concrete complexity bounds for optimizing over integers
We discuss the complexity of the two main ingredients in integer optimization algorithms: cutting planes and branch-and-bound. We prove upper and lower bounds on the efficiency of these algorithms, when efficiency is measured in terms of complexity of the LPs that are solved. More precisely, we focus on the sparsity of the LPs and the number of LPs as measures of complexity. We also give general conditions under which combining branching and cutting into a branch-and-cut algorithm can do exponentially better than pure cutting planes or pure branch-and-bound. Time permitting, some connections to mathematical logic and proof complexity will be discussed.
Friday 23 October - Ruilan Wang (LSE)
Identically self-blocking clutters
A clutter is identically self-blocking (ISBC) if it is equal to its blocker. It is proved by Abdi, Cornuéjols and Lee that every nontrivial identically self-blocking clutter is non-ideal. However the proof for this result is rather mysterious, which does not reveal much about the extreme points of the underlying polyhedron associated with the clutter. A minor characterisation conjecture for non-trivial ISBC was therefore proposed in the same paper by Abdi et al., which would be a strengthening of the above mentioned result. In this talk we will look at results on proving some special cases of this conjecture. Along the way, we will also discover an infinite family of ISBC arising from the clutter of st-T-joins and the clutter odd st-walks.
Thursday 22 October - Willemien Kets (University of Oxford)
How (Not) To Eat a Hot Potato
We study a matching problem where players are repeatedly assigned tasks. There are frictions in the matching process: players may be matched with undesirable tasks (``hot potatoes'') even if more attractive tasks (``sweet potatoes'') are available. There is a tradeoff between waiting for sweet potatoes and reducing matching frictions by accepting hot potatoes. Under the optimal mechanism, players accept hot potatoes as long as the relative cost of doing so is not too high. In decentralized settings, externalities and strategic complementarities can lead to welfare loss. We quantify the welfare gain of centralization, which can be substantial even when players are arbitrarily patient.
Friday 16 October - Johannes Brustle (LSE)
Robust Auctions and Uniform Convergence
Our goal is to make progress towards learning auctions from limited access to value distributions. In this setting, we know that the VC dimension cannot be used to efficiently obtain the uniform convergence property with respect to the empirical distribution. In fact a more refined tool, the Rademacher Complexity, also requires an exponential number of sample points in the dimension to satisfy uniform convergence. However, given access to approximations of the true value distributions, we still manage to construct robust auctions that are oblivious to the true distribution, yet yield close to optimal revenue.
Thursday 15 October - Ben Moseley (Carnegie Mellon University)
Combinatorial Optimization Augmented with Machine Learning
Combinatorial optimization often focuses on optimizing for the worst-case. However, the best algorithm to use depends on the "relative inputs", which is application specific and often does not have a formal definition.
The talk gives a new theoretical model for designing algorithms that are tailored to inputs for the application at hand. In the model, learning is performed on past problem instances to make predictions on future instances. These predictions are incorporated into the design and analysis of the algorithm. The predictions can be used to achieve "instance-optimal" algorithm design when the predictions are accurate and the algorithm's performance gracefully degrades when there is an error in the prediction.
The talk will apply this framework to applications in online algorithm design and give algorithms with theoretical performance that goes beyond worst-case analysis. The majority of the talk will focus on load balancing in the restricted assignment machine scheduling model.
Friday 9 October - Zhuan Khye Koh (LSE)
A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
In this talk, I will present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality. The algorithm is based on the Newton–Dinkelbach method for fractional combinatorial optimization, and extends previous work of Madani (2002). The key technical idea is a new analysis of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm. This also leads to an acceleration of the method for general fractional combinatorial optimization problems. Based on joint work with Bento Natura and László Végh.
Thursday 1 October - Maria Chudnovsky (Princeton University)
Induced subgraphs and tree decompositions
Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction; the talk will be a survey of these results.
Seminar and PhD Seminar on Combinatorics, Games and Optimisation:
2019/20
Seminar on Combinatorics, Games and Optimisation
2018/19, 2017/18, 2016/17, 2015/16
The Seminar on Combinatorics, Games and Optimisation started in 2016. It is a combination of two previous seminar series:
Seminar on Discrete Mathematics and Game Theory:
2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003
Seminar on Operations Research:
2016, 2015, 2014, 2013, 2012, 2011, 2010
PhD Seminar on Combinatorics, Games and Optimisation:
2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012