Belated Congratulations to Navin Rustagi
July 19, 2010, 2:36 pm
Filed under: Uncategorized | Tags: , , ,

Navin successfully defended his dissertation on July 8th and has recently had his final manuscript accepted.  Below is the announcement for his defense, preserved for posterity đŸ™‚Â  Some of his research results have already been discussed in his previous guest blog posts.
Congratulations Navin!

PhD Dissertation Defense  Presented by: Navin Rustagi
Title: Security in Network Games

Committee Chair:
Jared Saia, Associate Professor of Computer Science at UNM
Committee Members:
James Aspnes, Professor of Computer Science at Yale University
Josep Diaz, Universitat Politecnica de Catalunya
Tom Hayes, Assistant Professor of Computer Science at UNM


Attacks on the Internet are characterized by several alarming trends:
1) increases in frequency; 2) increases in speed; and 3) increases in
severity.  Modern computer worms simply propagate too quickly for human
detection. Since attacks are now occurring at a speed which prevents
direct human intervention, there is a need to develop automated
defenses. Since the financial, social and political stakes are so
high, we need defenses which are provably good against a worst
case attacks and are not too costly to deploy. In this talk we
present two approaches to tackle these problems.

For the first part of the talk we consider a game between an alert and
a worm over a large network. We show, for this game,
that it is possible to design an algorithm for the alerts that can
prevent any worm from infecting more than a vanishingly small fraction of the
nodes with high probability. Critical to our result is designing
a communication network for spreading the alerts that has high
expansion. The expansion of the network is related to the gap between
the $1^{st}$ and $2^{nd}$ eigenvalues of the adjacency
matrix. Intuitively high expansion ensures redundant connectivity. We
also present results simulating our algorithm on networks of size up to

In the second part of the talk we consider the virus inoculation game
which models the selfish behavior of the nodes involved. We present a technique for this game which makes it possible to achieve the “windfall of malice” even without
the actual presence of malicious players. We also show the limitations
of this technique for congestion games that are known to have a windfall of malice.

This dissertation includes research previously published in WINE and OPODIS.

April 2, 2010, 8:04 pm
Filed under: Uncategorized | Tags: , , , ,

Congratulations to my student Dr. Amitabh Trehan who just defended his dissertation yesterday (on April Fool’s Day no less). Amitabh has done some very nice work on self-healing in networks, published in the last two PODC’s and in IPDPS. He’ll be doing a short post doc for several months with Valerie King at U. Victoria and then will be doing a year-long post doc with Shay Kutten at Technion. Congratulations Amitabh!!!

A one slide dissertation summary: