Midwest Theory Day Next Meeting: Dec. 6, 2008, 10am-5:00pm, Fine Barr Forum, Allen Center, Northwestern U., Evanston IL.

Next Meeting: Dec. 6, 2008, 10am-5:00pm, Fine Barr Forum, Allen Center, Northwestern U., Evanston IL.

Registration

Invited Talk

Speaker: Abraham Flaxman (Institute for Health Metrics and Evaluation, Seattle, WA.)

Title: Theoretical Computer Science for Global Health

Abstract: Spanning Trees, Random Graphs, Markov Chains, and Solving Linear System of Equations: these bread-and-butter concepts from CS theory all have important roles to play in understanding global health. In this talk, I'll give an overview of the Global Burden of Disease Study (GBD), and describe some of its many algorithmic challenges. GBD is a systematic effort to produce estimates of how 200+ diseases, injuries, and risk factors impact people around the world. Naturally, there are a lot of numbers to crunch. But you may be surprised to learn how many of the relevant numbers are missing. And the numbers we do have often don't add up. This is where we need computational tools, and I hope to leverage research from probability theory, machine learning, and possibly even combinatorial Hodge theory. I'll give you a quick tour of the interdisciplinary area that is Health Metrics.

Bio: For the last 3 months, Abraham Flaxman has been working as a post-doc at the Institute for Health Metrics and Evaluation, which does global health research as part of the Public Health School at the University of Washington. Before that, he was a graduate student at CMU and a post-doc in the Microsoft Research Theory Group. He maintains a weblog about Math, CS, and OR applications to Health Metrics at http://healthyalgorithms.wordpress.com/.

We consider the following "multiway cut packing" problem in undirected graphs: we are given a graph G=(V,E) and k commodities, each corresponding to a set of terminals located at different vertices in the graph; our goal is to produce a collection of cuts {E_1,...,E_k} such that E_i is a multiway cut for commodity i and the maximum load on any edge is minimized. The load on an edge is defined to be the number of cuts in the solution crossing the edge. In the capacitated version of the problem the goal is to minimize the maximum relative load on any edge--the ratio of the edge's load to its capacity. Multiway cut packing arises in the context of graph labeling problems where we are given a partial labeling of a set of items and a neighborhood structure over them, and, informally, the goal is to complete the labeling in the most consistent way. We present the first constant factor approximation for this problem in arbitrary undirected graphs. Our approach is based on the observation that every instance of the problem admits a near-optimal laminar solution (that is, one in which no pair of cuts cross each other).

Joint work with Shuchi Chawla

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph. This representation has been used to develop the first dynamic graph algorithm for interval graphs.

In many settings, competing technologies -- for example, operating systems, instant messenger systems, or document formats -- can be seen adopting a limited amount of compatibility with one another; in other words, the difficulty in using multiple technologies is balanced somewhere between the two extremes of impossibility and effortless interoperability. There are a range of reasons why this phenomenon occurs, many of which -- based on legal, social, or business considerations -- seem to defy concise mathematical models. Despite this, we show that the advantages of limited compatibility can arise in a very simple model of diffusion in social networks, thus offering a basic explanation for this phenomenon in purely strategic terms. Our approach builds on work on the diffusion of innovations in the economics literature, which seeks to model how a new technology A might spread through a social network of individuals who are currently users of technology B. We consider several ways of capturing the compatibility of A and B, focusing primarily on a model in which users can choose to adopt A, adopt B, or -- at an extra cost -- adopt both A and B. We characterize how the ability of A to spread depends on both its quality relative to B, and also this additional cost of adopting both, and find some surprising non-monotonicity properties in the dependence on these parameters: in some cases, for one technology to survive the introduction of another, the cost of adopting both technologies must be balanced within a narrow, intermediate range. We also extend the framework to the case of multiple technologies, where we find that a simple model captures the phenomenon of two firms adopting a limited "strategic alliance" to defend against a new, third technology.

Joint work with J. Kleinberg, M. Mahdian, and T. Wexler.

In symmetric 2-party secure function evaluation, Alice has an input $x$, Bob has an input $y$, and both parties wish to compute $f(x,y)$ without revealing anything more about $x$ and $y$ to each other.

It has been known that not all functions $f$ can be securely computed with computationally unbounded players (i.e., without computational assumptions).

We give a precise combinatorial characterization of functions that can be securely computed with computationally unbounded players. Further we show a hierarchy of functions of strictly increasing ``cryptographic complexity:'' given oracle access to computing a lower complexity function, it is still impossible to compute the higher complexity functions.

Joint work with Manoj Prabhakaran and Mike Rosulek.

We study the multicast capacity of a random wireless network consisting of ordinary wireless nodes and base stations, known as a hybrid network. Assume that n ordinary wireless nodes are randomly deployed in a square region and all nodes have the uniform transmission range r and uniform interference range R=cr where c is some constant. We further assume that each ordinary wireless node can transmit/receive at W_a-bps. In addition, there are m additional base stations (neither source nodes nor receiver nodes) placed uniformly in this square region. Each base station can communicate with adjacent base stations directly with a data rate W_B-bps and the data transmission rate between a base station and a wireless node is assumed to be W_c-bps. Assume that there is a random set of n_s nodes that will serve as the source nodes of n_s multicast flows (each has randomly selected k-1 receivers). We found that the multicast capacity for hybrid networks has three regimes and for each of regime, we derive the matching asymptotic upper and lower bounds.

Joint work with Xiang-Yang Li and Shaojie Tang.

We consider two scheduling models: First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum delay factor. The delay factor of a schedule is defined to be the minimum alpha >= 1 such that each request i is completed by time a_i + alpha(d_i - a_i ) where a_i is the arrival time of request i and d_i is its deadline. Delay factor generalizes the previously defined measure of maximum stretch which is based only on the processing times of requests.

We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. Motivated by this, we consider resource augmentation analysis and prove the following positive results. For the unicast model we give algorithms that are (1 + \eps)- speed O(1/\eps)-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for same-sized pages that is (2 + \eps)-speed O(1/\eps^2)-competitive. For arbitrary page sizes we give an algorithm that is (4 + \eps)-speed O(1/\eps^2)-competitive.

Joint work with Chandra Chekuri.

New technologies for collecting genotypic data from natural populations open the possibilities of investigating many fundamental biological phenomena, including behavior, mating systems, heritabilities of adaptive traits, kin selection, and dispersal patterns. The power and potential of genotypic information often rests in the ability to reconstruct genealogical relationships among individuals. These relationships include parentage, full and half-sibships, and higher order aspects of pedigrees. Some areas of genealogical inference, such as parentage, have been studied extensively. Although methods for pedigree inference and kinship analysis exist, most make assumptions that do not hold for wild populations of animals and plants. We present new combinatorial formulations and their complexity results, including a link to Raz's Parallel Repetition Theorem.

Joint work with Tanya Berger-Wolf, Bhaskar DasGupta, and Ashfaq Khokhar.

In this talk, I will discuss constrained $\ell_1$ minimization methods in a unified framework for the recovery of high dimensional sparse signals in three settings: noiseless, bounded error and Gaussian noise. I will describe some improvements to the existing results in the literature by weakening the RIP conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. I will also discuss connections between restricted isometry property and the mutual incoherence property, and present some extensions to the results of Candes, Romberg and Tao, and Donoho, Elad, and Temlyakov.

Joint work with Tony Cai and Jun Zhang

Data aggregation is a key functionality for wireless sensor network (WSN) applications. This paper focuses on data aggregation scheduling problem to minimize the latency. We propose an efficient distributed scheduling method that produces a collision-free schedule to perform data aggregation in WSNs. We theoretically prove that the latency of the aggregation schedule generated by our algorithm is at most $13R+\Delta-12$. Here $R$ is the network radius and $\Delta$ is the maximum node degree in the communication graph of the original network. Our method significantly improves the previously known best data aggregation algorithm which has a latency bound $24D+6\Delta+16$, where $D$ is the network diameter. We conduct extensive simulations to study the practical performances of our proposed data aggregation methods. Our simulation results corroborate our theoretical results and show that our algorithms perform better in practice.

• The Homestead [map it]
  1625 Hinman Ave,
  Evanston, IL
  (847) 475-3300

  Mention "Midwest Theory Day" when booking to get a room rate of $95 per night that includes: complimentary parking, complimentary continental breakfast, wireless high speed Internet access, guest laundry, cable TV, iron and ironing board.

  Some double rooms are available at the same rate.

• Best Western University Plaza [map it]
  1501 Sherman Ave,
  Evanston, IL
  (847) 491-6400

  Mention "Midwest Theory Day" when booking to get a room rate of $89 per night that includes: complimentary wireless Internet, TV's with free Sho-time, coffee maker, iron, ironing board and hair dryers, and free shuttle ride to NU.

  Double rooms are available at the same rate.

Dinner will be at Mt. Everest at 630 Church St., Evanston, IL 60201. See map, below.