The 58th Midwest Theory Day Saturday, April 25, 2009 at the University of Wisconsin-Milwaukee

Invited Talk

Speaker: Lance Fortnow, Northwestern University.

Title: The Status of the P versus NP Problem

Abstract: We will look at how people have tried to solve the P versus NP problem and also how this question has shaped so much of the research in computer science and beyond. This talk is based on an upcoming survey article to appear in the Communications of the ACM.

Bio: Prof. Lance Fortnow received his Ph.D. in Applied Mathmatics at MIT in 1989 under the supervision of Michael Sipser. After two stints at the University of Chicago (spending four years at the NEC Research Institute in-between), Fortnow started as a Professor in the Electrical Engineering and Computer Science Department at Northwestern University in January of 2008.

Fortnow's research spans computational complexity and its applications. His major results on interactive proof systems and time-space lower bounds for satsifability have led to his election as a 2007 ACM Fellow. In addition he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97 where he spent a productive sabbatical year at CWI and the University of Amsterdam.

Among his many activities, Fortnow is the founding editor-in-chief of the ACM Transaction on Computation Theory and serves as vice-chair of ACM SIGACT, and served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog in the fall of 2003, the first major theoretical computer science blog.

We consider the unsplittable flow problem (UFP) and the closely related column-restricted packing integer programs (CPIPs). In UFP we are given an edge-capacitated graph $G=(V,E)$ and $k$ request pairs $R_1, \ldots, R_k$ where each $R_i$ consists of a source-destination pair $(s_i,t_i)$, a demand $d_i$ and a weight $w_i$. The goal is to find a maximum weight subset of requests that can be routed unsplittably in $G$. Most previous work on UFP has focused on the case where the maximum demand of the requests is no larger than the smallest edge capacity -- referred to as the no-bottleneck assumption; we use UFP-NBA to refer to UFP with this restriction. Inspired by the recent work of Bansal et al. on UFP on a path without the above assumption, we consider UFP on paths as well as trees. We give a simple $O(\log n)$ approximation for UFP on trees when all weights are identical; this yields an $O(\log^2 n)$ approximation for the weighted case. These are the first non-trivial approximations for UFP on trees. Using our insights, we develop an LP relaxation for UFP on paths that has an integrality gap of $O(\log^2 n)$; previously there was no relaxation with $o(n)$ gap. Motivated by our results for trees, we consider UFP in general graphs and CPIPs without the no-bottleneck assumption and obtain new and useful results.

Joint work with Chandra Chekuri and Nitish Korula.

Reserve-price based auctions are widely prevalent, e.g., eBay, adWords, and Sotheby's. While the Nobel prize wining result of Roger Myerson shows that in simple settings, reserve-price based auctions are optimal for the seller, they are not in more realistic settings. We show that in very general settings, reserve-price based auctions are close to optimal.

Joint work with Tim Roughgarden.

In the classical secretary problem, one picks a single element from a sequence of elements appearing online in a random order. One must decide immediately after seeing any element (before seeing the next element) whether to pick it; once made, a decision cannot be changed. The goal is to maximize the probability of picking the largest element. A well-known algorithm has probability 1/e of picking this element. In several generalizations of the problem, each element has a weight and the goal is to pick a maximum-weight "independent" set of elements, for a suitable definition of independence. For example, in the k-secretary problem, the goal is to pick a set of at most k elements with maximum total weight. In the matroid secretary problem, a matroid is defined on the elements and the goal is to pick a maximum-weight independent set in the matroid.

We study various problems seeking maximum-weight matchings in graphs and hypergraphs where edges and vertices are presented in online fashion, giving constant-competitive algorithms for all these problems in hypergraphs of bounded edge-size. These have applications to online ad allocation. We also give improved O(1)-competitive algorithms for the graphic matroid and transversal matroid secretary problems.

Joint work with Martin Pál.

This paper presents fast, distributed approximation algorithms for the metric facility location problem in CONGEST model, where message sizes are bounded by O(log N) bits, N being the network size. We first show how to obtain a 7-approximation in O(log m + log n) rounds via the primal-dual method; here m is the number of facilities and n is the number of clients. Subsequently, we generalize this to a k-round algorithm, that for every constant k, yields an approximation factor of O(m^{2/\sqrt{k}} n^{2/\sqrt{k}}). These results answer a question posed by Moscibroda and Wattenhofer (PODC 2005). Our techniques are based on the primal-dual algorithm due to Jain and Vazirani (JACM 2001) and a rapid randomized sparsification of graphs due to Gfeller and Vicari (PODC 2007). These results complement the results of Moscibroda and Wattenhofer (PODC 2005) for non-metric facility location and extend the results of Gehweiler et al. (SPAA 2006) for uniform metric facility location.

Joint work with Sriram Pemmaraju.

Kinship Analysis from microsatellite markers is an important area of population genetics with applications in conservation biology, kin selection, evolutionary biology and agriculture. Computationally, this area poses a number of interesting problems, especially when modeled with combinatorial optimization. The goal is given genotypic data of a cohort of individuals, reconstruct kinship information including sibling groups and parental genotype. We will discuss the combinatorial problem of reconstructing minimum half-sibling groups (i.e. groups of individuals that share one parent) necessary to explain a population. In addition to the applications of such information we will discuss an exact algorithm, complexity, and finally the relation of the problem to Raz's Parallel Repetition Theorem.

In this talk, we shall describe a family of conditions that ensure the reconstruction of sparse signal via L1 Minimization, for compressed sensing matrices. These conditions are weaker than what is known in the literature. We will include a discussion on the Shifting Inequality, which is a key technical tool for deriving these sparse recovery conditions.

Joint work with Tony Cai and Lie Wang.

• The Astor Hotel
• The County Clare Inn