Below you'll find an overview of the past seminars in this series from 2014. The seminars are listed in reverse chronological order, most recent first.
Thursday 11 December - Jop Briet| (NYU/CWI)
Locally Decodable Codes and Geometry of Banach Spaces
Locally decodable codes (LDCs) are error correcting codes that allow any single symbol of an encoded message to be retrieved by querying only a small number of randomly selected codeword symbols, even if the codeword is partially corrupted. A main open problem is to determine what is the smallest-possible codeword length of such codes when the query complexity is a fixed constant. This talk is about a link between that problem and geometric properties of certain Banach spaces that has implications in two directions. In one direction, the link gives short alternative proofs of essentially all known lower bound on the length LDCs. In the other direction, it gives an alternative route to a result of Briet, Naor and Regev on the geometry of tensor products of l_p spaces. More generally, the link suggests a new approach to proving LDC lower bounds by showing that certain finite-dimensional Banach spaces cannot contain high-dimensional copies of l_1 with small distortion.
Thursday 4 December - Klas Markström| (Umeå Universitet)
Full subgraphs
Given a graph G with n vertices and edge density p, a subgraph H on k vertices is said to be full if the minimum degree of H is at least p(k-1). Our basic question is: How large is the largest full subgraph of G? Erdös, Luczak and Spencer showed that if p=1/2 then the answer is at least of order n^0.5 and there are graphs where it less than n^(2/3)log(n)^(1/3). The lower bound is given by a constructive greedy algorithm
In this talk I will discuss my recent joint work on this problemwith Victor Falgas-Ravry and Jacques Verstraete. Among other things we prove that for p=1/2 the optimal upper and lower bounds are of order n^(2/3). We also show that the simple greedy algorithm can fail to give a full subgraph of the optimal order and that there is another algorithm which finds a full subgraph of the same order as the optimal one.
Thursday 27 November - Costantinos Daskalakis| (MIT)
Computing on Strategic Inputs
Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e.optimizing over rational inputs) to algorithm design(i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.
Bio: Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and its interface with economics and probability. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, and the 2012 Microsoft Research Faculty Fellowship. He is also a recipient of Best Paper awards at the ACM Conference on Economics and Computation in 2006 and in 2013.
Thursday 20 November - Ilias Diakonikolas| (Edinburgh)
Algorithmic Approaches to Statistical Estimation under Structural Constraints
The area of inference under structural (or shape) constraints -- that is, inference about a probability distribution under the constraint that its density function satisfies certain qualitative properties -- is a classical topic in statistics and machine learning.
Shape restricted inference has seen a recent surge of research activity, in part due to the ubiquity of structured distributions in the natural sciences. The hope is that, under such structural constraints, the quality of the resulting estimators may dramatically improve, both in terms of sample size and in terms of computational efficiency.
In this talk, I will describe a framework that yields new, provably efficient estimators for several natural and well-studied classes of distributions. This approach relies on a single, unified algorithm that provides a fairly complete picture of the sample and computational complexities for fundamental inference tasks. The focus of the talk will be on density estimation (learning), but I may also discuss applications of these ideas to hypothesis testing.
Tuesday 18 November - Eilon Solan| (Tel Aviv University)
Stopping games with termination rates
Multiplayer stopping game with termination rates are continuous-time stopping games in which when some players stop at the time interval $[t,t+dt)$, the game does not terminate with probability 1, but rather stops with some probability, which is of the order of $dt$ and may depend on time and on the set of players who stop at that time. We prove that every multiplayer stopping game with termination rates admits an $\ep$-equilibrium, for every $\ep > 0$.
Thursday 13 November - Dan Kral |(University of Warwick)
Complex structure of simple combinatorial limits
The recent theory of combinatorial limits has opened new links between analysis, combinatorics, computer science, group theory and probability theory. The talk will be focused on limits of two particular types of discrete objects - permutations and graphs. Motivated by applications in extremal combinatorics, Lovasz and Szegedy (2011) conjectured that every finitely forcible (describable) graph limit must be well-structured. We will disprove the conjecture using a new method for constructing finitely forcible combinatorial limits we developed.
The talk will be self-contained and no previous knowledge of the area is needed.
Thursday 6 November - Thomas Kesselheim| (Max Planck, Saarbruecken)
Primal Beats Dual on Online Packing LPs in the Random-Order Model
We study packing linear programs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources.
First, we consider the following special case of online weighted matching: The vertices on the right-hand side of a bipartite graph are given in advance and the vertices on the left-hand side arrive online in random order. Whenever a vertex arrives, its adjacent edges with the corresponding weights are revealed and the online algorithm has to decide which of these edges should be included in the matching. We present a new algorithmic approach achieving competitive ratio e = 2.72... This matches the lower bound for the classical secretary problem.
For general packing LPs, we present an online algorithm with competitive ratio $1-O(\sqrt(log d / B)), where d denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1 - \epsilon)-approximation if the capacity ratio satisfies B=\Omega(log d / \epsilon^2), which is known to be best-possible for any (randomized) online algorithms.
Joint work with Klaus Radke, Andreas Tönnis, and Berthold Vöcking, RWTH Aachen University.
Thursday 30 October - Claire Mathieu| (ENS Paris, Brown University)
On the Glass Ceiling Effect in Social Networks
The glass ceiling may be defined as “the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements”. Although undesirable, it is well documented that many societies and organizations exhibit a glass ceiling. In this paper we formally define and study the glass ceiling effect in social networks and provide a natural mathematical model that (partially) explains it. We propose a biased preferential attachment model that has two type of nodes, and is based on three well known social phenomena: i) rich get richer (preferential attachment) ii) minority of females (or other group) in the network and iii) homophily (preference to bond with similar people). We prove that our model exhibits a strong glass ceiling effect and that all three conditions are necessary, i.e., removing any one of them, will cause the model not to exhibit a glass ceiling effect. Additionally we present empirical evidence of student-mentor networks of researchers that exhibits all the above properties: female minority, preferential attachment, homophily and a glass ceiling.
Joint work with Chen Avin, Barbara Keller, Zvi Lotker, David Peleg, and Yvonne-Anne Pignolet.
Thursday 23 October - Elizabeth Baldwin| (LSE)
The geometry of auctions and competitive equilibrium with indivisible goods
In order to develop new auctions for related but different indivisible goods, we study how an agent's demand changes as prices change. Simple geometric properties translate directly to economic properties, providing a new taxonomy for agents' valuations, and new results about when competitive equilibrium exists.
This is joint work with Paul Klemperer (Oxford University).
Thursday 16 October - Paul Goldberg| (University of Oxford)
Learning game-theoretic equilibria via query protocols
In the traditional model of algorithmically solving a game, the entire game is the "input data", which is presented in its entirety to an algorithm that is supposed to compute a solution, for example an exact/approximate Nash/correlated equilibrium. In some situations it may be preferable to regard the game as a "black box" which the algorithm can find out about via queries. For example, a complete description of a multi-player game may be infeasibly large. In this talk, we give an overview of recent work on algorithms that find game-theoretic equilibria via a sequence of queries that specify pure-strategy profiles, and answer with the associated payoffs. The main research issue is "query complexity", which refers to how many queries are needed in order to find a given kind of solution.
Thursday 9 October - Arkadi Predtetchinski| (Maastricht University)
Subgame-perfect epsilon-equilibria in perfect information games with common preferences at the limit
We prove the existence of a pure subgame-perfect epsilon-equilibrium, for every epsilon >0, in multi-player perfect information games, provided that the payoff functions are bounded and exhibit common preferences at the limit. If, in addition, the payoff functions have finite range, then there exists a pure subgame-perfect 0-equilibrium. These results extend and unify the existence theorems for bounded and semicontinuous payoffs in Flesch et al [2010] and Purves and Sudderth [2011].
This is joint work with Janos Flesch.
Thursday 3 July - Paul Duetting| (Stanford)
Mechanisms for Matching Markets with Budgets
In this talk we review several recent results regarding matching markets with budgets. We begin by establishing the existence of a bidder optimal (BO) and envy free (EF) outcome for general non-linear and discontinuous utilities. Afterwards we prove that if these utilities satisfy a certain non-degeneracy assumption, then every mechanism that computes a BO and EF outcome is dominant strategy incentive compatible. We conclude by showing how a BO and EF outcome can be computed in polynomial time for piece-wise linear utilities with non-identical slopes and multiple discontinuities.
Based on joint work with Monika Henzinger and Ingmar Weber.
Thursday 26 June - Omer Edhan| (Manchester)
Cost Sharing with Dependencies
Two common assumptions in many works on cost sharing are 1. the lack of reciprocal demand constraints; namely, it is assumed that the set of feasible aggregate demand vectors is a rectangle, and 2. the cost function is (essentially) differentiable. This is not the case in many cost problems of interest, such as cost sharing in networks and risk sharing. Haimanko (2002) addressed the second matter but not the first, and his methods can not be extended to treat the first matter. We consider two classes of cost problems with no such restriction on demand vectors, and essentially non-differentiable cost functions. The cost functions in the first class are convex exhibiting non-decreasing marginal costs to scale, and those in the second class are piecewise linear. We prove existence and uniqueness of a cost allocation mechanism, satisfying standard axioms, on these classes. If time allows, generalizations of these results will be discussed.
Thursday 19 June - Matthew Jennsen (LSE)
A Hypergraph Turán theorem via a generalised notion of Lagrangian
Abstract: not available
Thursday 12 June - Eoin Patrick Long| (Oxford)
Frankl-Rödl type theorems for codes and permutations
How large can a family ${\cal A} \subset {\cal P}[n]$ be if $|A \cap B| \neq t$ for all $A,B \in {\cal A}$? The Frankl-Rödl theorem shows that if $0 < \epsilon n< t < (1/2-\epsilon )n$ then $|{\cal A}| \leq (2-\delta )^n$, where $\delta = \delta (\epsilon )> 0$. In this talk I will describe a new proof of this theorem. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl.
One consequence of this result is a Frankl-Rödl type theorem for permutations with a forbidden distance.
Joint work with Peter Keevash.
Thursday 29 May - Jan Foniok| (Warwick)
Deciding the Bell Number for Hereditary Graph Classes
The \emph{speed} of a hereditary graph class is the number of (labelled) graphs on {1,2,…,n} in the class, as a function of n. It is known that not every function can be obtained as the speed of some such class; e.g., if the speed grows faster than any polynomial, than it is at least exponential.
Another such jump was identified by Balogh--Bollobas--Weinreich (2005): if the speed is at least n(1−o(1))n, then it is bounded from below by the nth Bell number (the number of partitions of an n-element set). We study the computational problem to decide for a given hereditary class whether its speed is below or above* the Bell number.
We provide an algorithm that solves this problem for classes described by a finite list of forbidden induced subgraphs. It is based on a characterisation of minimal classes with speed above* the Bell number.
* By “above” I mean “greater than or equal to”.
Joint work with A Atminas, A Collins, V Lozin.
Thursday 8 May - Jeroen Schillewaert |(Imperial College)
Probabilistic Constructions in Finite Geometries
In ongoing work, we study random constructions of small maximal independent sets in incidence structures. To illustrate our ideas, I will discuss a well-studied example from finite geometry. No background on the latter will be assumed.
Joint work with Jacques Verstraete.
Thursday 1 May - Krzysztof R. Apt| (CWI and University of Amsterdam)
Selfishness Level of Strategic Games
We introduce a new measure of the discrepancy in strategic games between the social welfare in a Nash equilibrium and in a social optimum, that we call selfishness level. It is the smallest fraction of the social welfare that needs to be offered to each player to achieve that a social optimum is realized in a pure Nash equilibrium. The selfishness level is unrelated to the price of stability and the price of anarchy.
We study the selfishness level of several well-known strategic games. This allows us to quantify the implicit tension within a game between players' individual interests and the impact of their decisions on the society as a whole. Our analyses reveal that the selfishness level often provides a deeper understanding of the characteristics of the underlying game that influence the players' willingness to cooperate.
For instance, the selfishness level of the n-players Prisoner's Dilemma is c/(b(n-1)-c), where b and c are the benefit and cost for cooperation, respectively, and that of the n-players public goods game is (1-cn)/(c-1), where c is the public good multiplier. In turn, the selfishness level of Cournot competition, Tragedy of the Commons, and Bertrand competition is infinite.
This is a joint work with Guido Schaefer.
Thursday 20 March - Richard Montgomery| (Cambridge)
Spanning Trees in Random Graphs
Following on from the sharp determination of the threshold for a Hamiltonian path appearing in an Erdos-Renyi random graph, attention has been given to more general questions about the threshold for the appearance of other bounded degree spanning trees. We will outline a recent reduction of the probability required to embed a bounded degree spanning tree in a random graph, as well as mentioning the related problem of finding all such trees simultaneously.
Thursday 13 March - Jacques Verstraete| (University of California, San Diego)
Generalized factors of graphs
Abstract|
Thursday 6 March - Yoram Bachrach| (Microsoft Research, Cambridge)
On Agent Failures and Decomposing The Intelligence of Crowds
Cooperative game theory deals with selfish agents who need each other to achieve their goals, but who want to maximize their share of the total value generated. I'll demonstrate how solution concepts, such as the Shapley value or the core, can be used to measure the individual contribution of an agent to the intelligence of a crowd, and discuss how the potential for agent failures may actually help them collaborate.
Thursday 27 February
Barnaby Roberts (LSE)
A Random Graph Analogue of the Andrasfai-Erdos-Sos Theorem
Andrasfai, Erdos and Sos proved that all triangle-free graphs with minimum degree strictly greater than 2n/5 are bipartite. We consider an adaptation of this result to a random graph setting and discuss some other random graph versions of classical results.
This lecture forms part of the Lunchtime Seminar Series|.
Thursday 20 February - Eskil Rydhe| (Lund University, Sweden)
Weighted admissibility with respect to the right shift on H^{2}
Abstract|
Thursday 13 February - Marina Iliopoulou (University of Edinburgh)
The polynomial method in computational geometry
Recently, algebraic techniques have been introduced to count incidences between lines and points. The main idea behind these methods is decomposing the space we are working in—and therefore of our original set of points as well— by the zero set of a polynomial. This enriches our setting with extra structure, allowing us to understand it better. Such techniques were first used in incidence geometry by Dvir, for the solution of the Kakeya problem in finite field settings. The aim of this talk is to give a taste of these techniques (including Dvir’s basic argument), via the study of the joints problem in $\mathbb{R}^n$.
More specifically, if $\mathfrak{L}$ is a finite set of lines in $\mathbb{R}^n$, we say that a point $x \in \mathbb{R}^n$ is a joint formed by $\mathfrak{L}$ if at least $n$ lines of $\mathfrak{L}$ are passing through $x$, such that their directions span $\mathbb{R}^n$. The joints problem asks for the optimal upper bound of the number of joints formed by $\mathfrak{L}$, depending only on the cardinality of $\mathfrak{L}$. The joints problem was solved in $\mathbb{R}^3$ by Guth and Katz, and later in $\mathbb{R}^n$ by Kaplan, Sharir and Shustin, and independently by Quilodran; all the solutions involved algebraic techniques. In particular, we will present Quilodran’s solution, which involves Dvir’s essential argument for his solution of the Kakeya problem in finite fields.
Thursday 6 February - Filip Moric| (EPFL Lausanne)
Upper bounds for the perimeter of plane convex bodies
Given a plane convex body S and another convex set C contained in S, it is a well known fact that per(C)\leq per(S). In other words, the largest possible perimeter of a convex body that lies inside another convex body S equals per(S). We raise the following more general question: Given a compact convex body S in the plane and k\in\mathbb N, how large can the sum of perimeters of k pairwise disjoint convex sets contained in S be? We conjecture that the sum is always bounded from above by per(S) + 2(k-1) diam(S), which would be tight. We prove this conjecture in the case when S is a square or an arbitrary triangle. A slightly weaker bound is obtained for general plane convex bodies. As a consequence, we establish a bound on the perimeter of a polygon with at most k reflex angles lying inside a given plane convex body. We will also discuss some other related problems.
Based on joint work with Alexey Glazyrin
Thursday 30 January - Ziv Hellman| (Bar Ilan University, Israel)
Graph value for cooperative games
We suppose that players in a cooperative game are located within a graph structure, such as a social network or supply route, that limits coalition formation to coalitions along connected paths within the graph. This leads to a generalisation of the Shapley value that is studied here from an axiomatic perspective. The resulting ‘graph value’ is endogenously asymmetric, with the automorphism group of the graph playing a crucial role in determining the relative values of players.
Joint work with Ron Peretz
Thursday 23 January - Dario Bauso| (Palermo)
Robust Mean-Field Games
Within the realm of mean field games under uncertainty, we study a population of players with individual states driven by a standard Brownian motion and a disturbance term. The contribution is three-fold: First, we establish a mean field system for such robust games. Second, we analyze robust mean field equilibria. Third, we show that the dimension of the mean field system can be significantly reduced by considering a functional of the first moment of the mean field process. Applications to production, opinion dynamics and cyber-physical systems will be discussed.
Based on joint work with Tamer Basar and Hamidou Tembine.
Thursday 16 January - Yufei Zhao| (MIT)
The Green-Tao theorem and a relative Szemerédi theorem
The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications.
One of the main ingredients in the proof is a relative Szemerédi theorem, which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. Our main advance is both a simplification and a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition suffices. I will explain the transference principle strategy used in the proof.
Based on joint work with David Conlon and Jacob Fox.