Tag Archives: my research

January 10, 2010 · 2:37 am

Health Care Reform, Accountability, Disparity

I got some good news for the weekend, an opinion piece that I wrote together with some of the other post-graduate fellows at IHME was published online as a Science e-letter. It is titled U.S. Health Care Reform: The Case for Accountability and it’s about the measuring the outputs, outcomes, and impacts of the reform, whatever shape they end up taking.

The part that I was especially interested in adding to the discussion appears in paragraphs 3 and 4, about what these some of these statistics look like currently:

Disparities in health outcomes in the U.S. are unacceptable. A healthy life expectancy at birth in the U.S. ranks behind 28 other developed countries (1). Sizable groups in the United States have mortality risks resembling those in sub-Saharan Africa (2), including urban blacks between the ages of 15 and 64 living in counties with high homicide rates.

On average, Asian women lived 21 years longer than high-risk urban black males in 2001 (2). Although life expectancy for most American women increased between 1983 and 1999, life expectancy for women in 180 counties in areas such as Appalachia, the Deep South, the southern Midwest, and Texas decreased by 1.3 years (3).

I made some figures to accompany this, which Science didn’t print, so I’ve included them for you here:

Probability of a 45 year-old male dying before age 65, 2001, from Murray et al., Eight Americas: Investigating mortality disparities across races, counties, and race-counties in the United States. PLoS Medicine 2006.

Female life expectancy in US counties, 1961-1999 from Ezzati et al., The reversal of fortunes: Trends in county mortality and cross-county mortality disparities in the United States. PLoS Medicine 2008.

9 Comments

Filed under global health, science policy

Tagged as , ,

December 17, 2009 · 12:16 am

ACO in Python: Shortest Paths in NetworkX

I’m supposed to be doing the final edits on the journal version of this old paper of mine (jointly with Greg Sorkin and David Gamarnik), but I’ve thought of a way to procrastinate.

Instead of checking the proofs that the length of the shortest path in my weigthed width-2 strip is \frac{p^2(1+p)^2}{(3p^2+1)} n, I’ll make a quick blog post about verifying this claim numerically (in python with networkx). This also gives me a chance to try out the new networkx, which is currently version 1.0rc1. I think it has changed a bit since we last met.

from pylab import *
from networkx import *

G = Graph()
for u, v in grid_2d_graph(100, 2).edges():
    G.add_edge(u, v, weight=rand() < .5)

wt, p = bidirectional_dijkstra(G, (0,0), (99,1))

Continue reading →

2 Comments

Filed under combinatorial optimization

Tagged as , , , ,

November 14, 2009 · 8:21 pm

Clustering with Shallow Trees

I’m updating my CV, and that reminded me that I meant to promote this cool clustering technique that I was a little bit involved in, Clustering With Shallow Trees.

This goes way back to about half-way through my post-doc at MSR, when statistical physicist Riccardo Zecchina was visiting for a semester, and was teaching me about all of the “intractable” optimization problems that he can solve using his panoply of propagation algorithms. In particular, he was working on algorithms for certain types of steiner tree optimization, and he had discovered that adding an extra constraint on the depth of the tree didn’t make the problem harder. (All variants of the problem he considers are NP-hard, but some are NP-harder than others.) Continue reading →

4 Comments

Filed under combinatorial optimization

Tagged as , , , ,

February 25, 2009 · 12:27 am

k-SAT and me

I’ve posted a new paper on random k-SAT on the arxiv.  This is work I did towards the end of my post-doctoral stint at Microsoft Reseach with Danny Vilenchik and Uri Feige.  It is an application of a cool technique that Danny and others came up with to study random instances above the satisfiability threshold that have been selected uniformly at random from satisfiable instances at that density. We use it to derive some bounds on the likely diameter of the set of satisfying solutions under this conditionally random distribution.  Unfortunately, I don’t think that there are too many global health applications for random k-SAT with k large.

That’s too bad, because Amin Coja-Oghlan has also recently posted a paper about k-SAT on the arxiv, which sounds very promising. In A better algorithm for random k-SAT, Amin presents (from the abstract):

a polynomial time algorithm that finds a satisfying assignment of F with high probability for constraint densities m/n<(1-\epsilon_k)2^k\ln(k)/k, where \epsilon_k \rightarrow 0. Previously no efficient algorithm was known to find solutions with non-vanishing probability beyond m/n=1.817.2^k/k.

His algorithm is a combinatorial, local-search type algorithm. I’ll try to find time to read the paper even if I don’t come up with a compelling application of k-SAT to health metrics.

1 Comment

Filed under probability, TCS

Tagged as ,

December 4, 2008 · 1:10 am

Midwest Theory Day and Me

I’ll be talking about “Theoretical Computer Science in Global Health” as the invited speaker at the Midwest Theory Day this Saturday (Dec. 6). It sounds like it will be a fun workshop, a one day deal at Northwestern Univesity. If you’re in the area, I think you should come on by.

1 Comment

Filed under global health, TCS

Tagged as , , ,

October 28, 2008 · 3:33 pm

Minimum Spanning Trees of Bounded Depth (Random)

I’ve got a new paper up on the arxiv.  David Wilson recently posted this joint work that was one of the last things I did during my post-doc at Microsoft.  It hasn’t been applied to health metrics yet, but maybe it will be.  Let me tell you the story:

A spanning tree is just what it sounds like, if you know that a tree is a graph with no cycles, and make a good guess that the spanning tree is a subgraph that is a tree “spans” all the vertices in the graph.  Minimum cost spanning trees come up in some very practical optimization problems, like if you want to build a electricity network without wasting wires.  It was in this exact context, designing an electricity network for Moravia, that the first algorithm for finding a minimum spanning tree was developed.

Public Domain image of a Minimum Spanning Tree, from Wikipedia

A Minimum Spanning Tree, from Wikipedia

The great thing about looking for a minimum spanning tree is that you don’t have to be sneaky to find it.  If you repeatedly find the cheapest edge which does not create a cycle, and add that to your subgraph, then this greedy approach never goes wrong.  When you can’t add any more edges, you have a minimum spanning tree.  Set systems with this property have been so fun for people to study that they have an intimidating name, matroids.  But don’t be intimidated, you can go a long way in matroids by doing a search-and-replace s/matroid/spanning tree/.

Continue reading →

3 Comments

Filed under combinatorial optimization, probability

Tagged as , ,