Saturday, May 11th, 2013

DePaul University (downtown campus)

Title: Socially Stable Matchings

Presenter: Georgios Askalidis, Northwestern University

Abstract: The project is about generalizing the classical stable matching model by augmenting it with a social graph. In doing so, we only allow for a subset of the pairs to be socially blocking and this way we can get socially stable matchings that are in some cases twice the size of stable matchings. We investigate the complexity of finding a maximum socially stable matching and we present an approximation algorithm and a tight hardness of approximation result.

Title: On the list decodability of random linear codes with large error rates

Presenter: Mary Wootters, University of Michigan

Abstract: It is well-known that a random q-ary code of rate \Omega(\epsilon^2) is list decodable up to radius (1 - 1/q - \epsilon) with list sizes on the order of 1/\epsilon^2, with probability 1 - o(1). However, until recently, a similar statement about random linear codes has until remained elusive. In a recent paper, Cheraghchi, Guruswami, and Velingker show a connection between list decodability of random linear codes and the Restricted Isometry Property from compressed sensing, and use this connection to prove that a random linear code of rate \Omega(\epsilon^2 / log^3(1/\epsilon)) achieves the list decoding properties above, with constant probability. We improve on their result to show that in fact we may take the rate to be \Omega(\epsilon^2), which is optimal, and further that the success probability is 1 - o(1), rather than constant. As an added benefit, our proof is relatively simple. Finally, we extend our methods to more general ensembles of linear codes. As an example, we show that randomly punctured Reed-Muller codes have the same list decoding properties as the original codes, even when the rate is improved to a constant.

Title: Non-Adaptive Group Testing and the Group Sum Design

Presenter: Gergely Balint, Illinois Institute of Technology

Abstract: In group testing we are trying to identify a (usually small) subset D of a (large) set N. In order to identify the elements of D we can test subsets (groups) of N, where we get an answer whether there's an element of D in the tested subset (group). We call a matrix M that describes a particular test-design a test-matrix. There's several recent papers on the topic. In our talk we will introduce non-adaptive group testing and in a few words existing best results. We will present new ideas and our own construction, the Group Sum Design - which takes existing 'good' test-matrices and constructively creates new test matrices of higher dimensions. Finally we will discuss the advantages of our design.

Title: Beyond Knights and Knaves

Presenter: Drew Onderko, University of Wisconsin at Milwaukee

Abstract: In the classic knights and knaves problem there are n people in a room, each of whom is either a knight or a knave. Knights always tell the truth while knaves always lie. Everyone in the room knows each other's identity. You are allowed to ask questions of the form "Person i, is person j a knight?" and you are told that there are more knights than knaves. How many questions are necessary and sufficient in the worst case to identify a knight? How about to determine everyone's identity?

In this talk we consider the knights and no-men problem, where a no-man is a person who al- ways answers "no". Assuming there are at least k knights, we show that choose(n-1, 2) - floor((k-2)(n-1)^2 / 2(k-1)) questions are necessary and sufficient in the worst case to identify a knight. We also show that n-2 questions suffice to identify a no-man, and choose(n-1, 2) - floor((k-2)(n-1)^2 / 2(k-1)) + n-2 questions suffice to identify everyone in the room. We also consider a generalization of the knights and knaves problem that captures most of the variants of the knights and knaves problem in the literature. In the agent labeling problem we wish to identify everyone's type; in the agent identification problem we wish to identify an agent having a particular type. We present results with regards to the fewest number of questions needed in the worst case to solve both the agent labeling and agent identification problems. Our tools and results are graph theoretic in nature.

Title: The Complexity of Poset Games: A Survey

Presenter: John Rogers, DePaul University

Games played on partially-ordered sets (posets) are one kind of game from the very large class of combinatorial games. Simple to describe (the best known example is NIM), various computational complexity questions concerning them have only recently been settled and many others remain. In this survery I will explain the structure of the games and present some of these new results.

Title: Simple Auctions for Risk-Averse Agents

Presenter: Darrell Hoy, Northwestern University

Abstract: We study simple and approximately optimal auctions for agents with a particular form of risk-averse preferences. We show that, for symmetric agents, the optimal revenue (given a prior distribution over the agent preferences) can be approximated by the first-price auction (which is prior independent), and, for asymmetric agents, the optimal revenue can be approximated by an auction with simple form.

Title: Distinguishing Vertices of Inhomogeneous Random Graphs

Presenter: Paolo Codenotti, University of Michigan

Abstract: Classical results show that simple combinatorial attributes such as the distance sequence and degree-based partitioning and refinement can be used to efficiently distinguish vertices of almost all graphs (Erdos-Renyi distribution) as well as almost all regular graphs (Babai-Erdos-Selkow, 1979, Bollobas 1982). These results yield efficient high-probability isomorphism tests for these graphs. In this talk we analyze the same attributes for random graphs that come from distributions that more closely model real-world networks (e.g. scale free). Our main result is in the setting were edges are chosen independently at random. We will discuss some applications of this results to specific models (in particular Stochastic Kronecker Product graphs, Leskovec-Chackrabarti-Kleinberg-Faloutsos, 2005), as well as possible extensions to the case where edges are dependent (e.g. preferential attachment graphs, Barabasi-Albert, 2002).

Title: Price of Anarchy for Commodity Dependent Latency Functions

Presenter: Junghwan Shin, Illinois Institute of Technology

Abstract: In this talk we consider the price of anarchy (PoA) in resource allocation problems where the cost function of a resource has a heterogeneous dependency on the load. In particular we consider the multi-commodity flow problem in a network where edges are associated with commodity-dependent delay function, an example being delays of the form $a_1 x_1 + x_2$ where $x_1$ and $x_2$ represents the flows  of  the two different commodities.