Georgia Institute of Technology College of Sciences

We consider rooted subgraphs in random graphs, i.e., extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. 
In 1989, Joel Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices.  
For the important strictly balanced case, Spencer also raised the fundamental question whether these conditions are necessary. 
We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open. 

TBA

One of the most challenging aspects of designing human sensitive systems is in designing systems that assist decision makers in applying an effective intervention to a large group of individuals. This design challenge becomes especially difficult when the decision maker must operate under scarce resources and only partial knowledge of how each individual will react to the intervention.

In this talk, I will consider this problem from the perspective of a clinician that is designing a personalized weight loss program. Despite this focus, the precision analytics framework I propose for designing these interventions is quite general and can apply to many settings where a single coordinator must influence agents who make decisions by maximizing utility functions that depend on prior system states, inputs, and other parameters that are initially unknown. This precision analytics framework involves three steps: first, a predictive model that effectively captures the decision-making process of an agent; second, an optimization algorithm to estimate this model’s parameters for each agent and predict their future decisions; and third, an optimization model that uses these predictions to optimize a set of incentives that will be provided to each agent. A key advantage of this framework is that the calculated incentives are adapted as new information is collected. In the case of personalized weight loss interventions, this means that the framework can leverage patient level data from mobile and wearable sensors over the course of the intervention to personalize the recommended treatment for each individual.

  I will present theoretical results that show that the incentives computed by this approach are asymptotically optimal with respect to a loss function that describes the coordinator's objective.  I will also present an effective decomposition scheme to optimize the agent incentives, where each sub-problem solves the coordinator's problem for a single agent, and the master problem is a pure integer program. To validate this method I will present a numerical study that shows this proposed framework is more cost efficient and clinically effective than simple heuristics in a simulated environment. I will conclude by discussing the results of a randomized control trial (RCT) and pilot study where this precision analytics framework was applied for personalizing exercise goals for UC Berkeley staff and students. The results of these trials show that using personalized step goals calculated by the precision analytics algorithm result in a significant improvement over existing state of the art approaches in a real world setting.