Below you'll find the programme for the Seminar on Combinatorics, Games and Optimisation (a joining together of the former Seminar on Discrete Mathematics and Game Theory and the former Seminar on Operations Research).
This semianr 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:
-
on Wednesdays from 4.00 pm - 5.00 pm in room TW1.2.03 (Tower One, LSE)
-
on Thursdays from 2.00 pm - 3.00 pm in room TW2.3.01 (Tower Two, LSE).
Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk.
Upcoming Speakers:
Wednesday 23 November - Itai Arieli (Technion)
How to aggregate information if you must?
The decisions an economic agent is required to make are often based upon the likelihood of an uncertain future event. We study the case where an ignorant agent can use predictions of experts over the likelihood of the event to form his own prediction. We ask how the agent should aggregate the information provided by the experts when he knows
Thursday 24 November - Neil Olver (VU Amsterdam)
A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
I will present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given in [Végh16]; our new algorithm is much simpler, and much faster. The complexity bound O((m+nlogn)mnlog(n2/m)) improves on the previous estimate in [Végh16] by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.
This is joint work with László Végh (LSE).
Wednesday 30 November - TBC
Thursday 1 December - TBC
***Change to usual day and venue***
Tuesday 6 December - 4pm-5pm - Herve Moulin (Glasgow)
Venue: TW2.1.03 (Tower Two, LSE)
Title and abstract TBC
Thursday 8 December - Clément Canonne (Columbia)
Alice and Bob Show Distribution Testing Lower Bounds (They don’t talk to each other anymore.)
We present a new methodology for proving distribution testing lower bounds, by establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple methodology of reducing lower bounds on (private-coin) SMP problems to distribution testing problems. This reduction allows us to prove several new distribution testing lower bounds, as well as to provide simpler proofs of known lower bounds.
Our main result is concerned with testing identity to a specific distribution p, given as a massive parameter. Valiant and Valiant [VV14] showed that the sample complexity of the foregoing question is closely related to the 2/3-pseudonorm of $p$. We obtain alternative, nearly tight bounds on the complexity of this problem, in terms of an arguably more intuitive measure and using simpler proofs. Specifically, we show that the sample complexity is essentially determined by the size of the effective support of p, which loosely speaking is the number of supported elements that constitute the vast majority of the mass of p.This result, in turn, stems from an unexpected connection to the theory of interpolation spaces, namely the K-functional between L_1 and L_2 spaces.
Previous seminars in this series: 2016
Seminar on Discrete Mathematics and Game Theory: 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004 and before
Seminar on Operations Research: 2016, September 2015 - December 2015, August 2014 - August 2015, October 2010 - July 2014