Below you'll find the program for the Lunchtime Seminar. The Seminar normally takes place on Fridays from 12.05 pm - 12.35 pm in room 32L.G.01 (32 Lincoln's Inn Fields). Follow this link for a map of the School.
Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator (Room COL 3.14), by sending an e-mail to: firstname.lastname@example.org
Friday 15 May - Vissarion Fisikopoulos (ULB)
Polyhedral computations in computational algebraic geometry and optimization
We study geometric algorithms and polyhedral computations for problems that appear in computational algebraic geometry and optimization.
The first motivation comes from polynomial system solving.
From this perspective (Newton) polytopes characterize polynomials better than total degree thus offering the fundamental representation in sparse elimination theory. We propose output-sensitive algorithms that require the minimum number of polytope oracle calls, each reducing to the construction of a regular triangulation of the input set of points. Their implementation has been used first in the experimental analysis of algorithms and second as a computational tool in our study of the combinatorial characterization of these polytopes.
Another motivation comes from optimization, where polytopes are the solution space of a set of linear inequalities. We study 2-level (or compressed) polytopes, i.e. all of whose pulling triangulations are unimodular. These polytopes can be realized as 0/1 polytopes and contain the class of stable set polytopes of perfect graphs. We propose and implement an algorithm based on formal concept analysis to enumerate all combinatorial types of 2-level polytopes. Experimental results are valuable in the study of their extremal properties and towards proving characterization results with the ultimate goal to be the study of their extension complexity.
Friday 22 May - Joonkyung Lee (Oxford)
Some Advances on Sidorenko's Conjecture
A bipartite graph $H$ is said to have Sidorenko's property if the probability that the uniform random mapping from $V(H)$ to the vertex set of any graph $G$ is a homomorphism is at least the product of the probabilities that each edge of $H$ is mapped into an edge in $G$. In this talk, I will give an overview of the known results and new approaches to attack Sidorenko’s conjecture, especially an embedding algorithm to prove that bipartite graphs admitting a specific form of tree decomposition have Sidorenko's property. This is joint work with David Conlon, Jeong Han Kim, and Choongbum Lee.
Friday 29 May - John Howard (LSE)
Exchanging Goods Using Valuable Money
A group of people wish to use money to exchange goods over a finite number of time periods. They consider using one of the goods as money, but none has suitable characteristics. They understand that traders are prepared to exchange goods for token money only because they believe that in the future they will be able to exchange the money for other goods. So, if society issues fiat money in the form of notes or coins, it will be valueless in the final time period, and hence in all earlier periods.
An alternative would be to allow the traders to create their own money (by writing promissory notes), but then the market equilibrium prices will be determined only up to an arbitrary rescaling. (If a set of prices clears the market, doubling all the prices will also give an equilibrium.) This may not matter in a one-period setting, but if there are several trading periods, it may cause problems.
Is it possible to devise a system which uses money to exchange goods, where money does not enter the traders' utility functions, but which yields a solution in which money has a unique positive value? I will discuss this question (Hahn's problem), and define such a mechanism in a very simple setting. The proposal involves some redistribution of wealth and some distortion of prices, but I will show that these effects can be made small.
Friday 5 June - seminar details TBA
Friday 12 June - seminar details TBA
Friday 19 June - seminar details TBA
Friday 26 June - seminar details TBA
Friday 3 July - seminar details TBA
Previous seminars in this series: 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006