April 8th, 2015
Stable Matching in Large Economies
Department of Economics, Seoul National University, Seoul, Korea
2015/5/12 Tue 4PM-5PM
Complementarities of preferences have been known to jeopardize the stability of two-sided matching, and they are a pervasive feature of many markets. We revisit the stability issue with such preferences in a large market.
Workers have preferences over firms while firms have preferences over distributions of workers and may exhibit complementarity. We demonstrate that if each firm’s choice changes continuously as the set of available workers changes, then there exists a stable matching even with complementarity. Building on this result, we show that there exists an approximately stable matching in any large finite economy. We extend our framework to accommodate indifferences in firms’ preferences, construct a stable mechanism that is strategy-proof and equitable for workers perceived as indifferent by firms, and apply the analysis to probabilistic and time-share matching models with a finite number of firms and workers.
April 7th, 2015
Space Proof Complexity for Random 3-CNFs
Dipartimento di Informatica, Sapienza Università di Roma, Rome, Italy
2015/6/2 Tue 4PM-5PM
During the last decade, an active line of research in proof complexity has been the space complexity of proofs and how space is related to other complexity measures (like size, length, width, degree). Space is (roughly) how large of an erasable board one would need to show a proof line-by-line.
Here, we are interested in the space complexity of refuting 3-CNFs (formulas in conjunctive normal form with at most 3 literals per clause). We prove that a random 3-CNF with n variables requires, with high probability, Ω(n2) total space in Resolution. This is best possible up to a constant factor.
This lower bound is obtained via a variant of Hall’s Lemma which may be of independent interest. Namely, we show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2-ε), for ε < 1/23.
This is joint work with Patrick Bennett, Ilario Bonacina, Nicola Galesi, Mike Molloy, and Paul Wollan.
March 30th, 2015
Computational Phase Transitions for the Potts Model
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2015/4/14 Tue 4PM-5PM
This is a followup talk to my CS colloquium on March 2
. In that talk I discussed the problems of counting independent sets and colorings. Those problems are examples of antiferromagnetic systems in which neighboring vertices prefer different assignments. In this talk we will look at ferromagnetic systems where neighboring vertices prefer the same assignment. We will focus on the ferromagnetic Potts model. We will look at the phase transitions in this model, and their connections to the complexity of associated counting/sampling problems and the performance of related Markov chains.
The talk is based on joint works with Andreas Galanis, Daniel Stefankovic, and Linji Yang.
March 25th, 2015
Combinatorics of orthogonal polynomials
2015/4/9 Thu 4:30PM-5:30PM (E6, Room 1501)
Orthogonal polynomials are a family of polynomials which are orthogonal with respect to certain inner product. The n-th moment of orthogonal polynomials is an important quantity, which is given as an integral. In 1983 Viennot found a combinatorial expression for moments using lattice paths. In this talk we will compute the moments of several important orthogonal polynomials using Viennot’s theory. We will also see their connections with continued fractions, matchings, set partitions, and permutations.
March 1st, 2015
Topological methods in matching theory
2015/4/7 Tue 4PM-5PM
Around 15 years ago, Aharoni and Haxell gave a wonderful generalization of Hall’s marriage theorem. Their proof introduced topological methods in matching theory which were further developed by Berger, Meshulam, and others. Recently, motivated by some geometric questions, we extended these methods further, and in this talk I’ll explain the ideas and some of our results.