[FYI] KAIST Theory Day (May 31, 2015)

May 11th, 2015

FYI: (KAIST Theory Day organized by Jinwoo Shin and Eric Vigoda)

KAIST Theory Day
2015/5/31 Sun 10AM-5PM (Room TBD, Bldg N1, KAIST)
9:30 – Coffee and refreshments
10:00 – Daniel Stefankovic (Rochester):  Spin models: connections between complexity, phase transition, belief propagation, and induced matrix norms
11:00 – Yitong Yin (Nanjing)Phase transition of hypergraph matchings
12:00 – Lunch break
1:30 – Euiwoong Lee (CMU):  Hardness of Graph Pricing through Generalized Max-Dicut
2:30 – Sewoong Oh (UIUC):  TBA
3:30 – Coffee break
4:00 – Martin Ziegler (TU Darmstadt):  Algebraic Complexity Theory and Quantum Logic

Pinyan Lu, Optimal Competitive Auctions

April 29th, 2015
Optimal Competitive Auctions
Pinyan Lu (陆品燕)
Theory Group, Microsoft Research Asia, Beijing, China
2015/5/19 Tue 4PM-5PM
We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic assumptions on buyers’ valuations and employs the framework of competitive analysis. Our objective is to optimize the worst-case performance of an auction, measured by the ratio between a given benchmark and revenue generated by the auction.
We establish a sufficient and necessary condition that characterizes competitive ratios for all monotone benchmarks. The characterization identifies the worst-case distribution of instances and reveals intrinsic relations between competitive ratios and benchmarks in the competitive analysis. With the characterization at hand, we show optimal competitive auctions for two natural benchmarks.
The most well-studied benchmark F^2 measures the envy-free optimal revenue where at least two buyers win. Goldberg et al. showed a sequence of lower bounds on the competitive ratio for each number of buyers n. They conjectured that all these bounds are tight. We show that optimal competitive auctions match these bounds. Thus, we confirm the conjecture and settle a central open problem in the design of digital goods auctions. As one more application we examine another economically meaningful benchmark, which measures the optimal revenue across all limited-supply Vickrey auctions. We identify the optimal competitive ratios to be (n/({n-1})^{n-1}-1 for each number of buyers n, that is e-1 as n approaches infinity.

Joint work with Ning Chen and Nick Gravin.

Jinwoo Kim (김진우), Stable Matching in Large Economies

April 8th, 2015
Stable Matching in Large Economies
Jinwoo Kim
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.

Tony Huynh, Space Proof Complexity for Random 3-CNFs

April 7th, 2015
Space Proof Complexity for Random 3-CNFs
Tony Huynh
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.

Eric Vigoda, Computational Phase Transitions for the Potts Model

March 30th, 2015
Computational Phase Transitions for the Potts Model
Eric Vigoda
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.