Research Budget Allocation
July 5, 2011, 5:33 pm
Filed under: Uncategorized | Tags: , ,

Some work of a recently graduated PhD student of mine, Amitabh Trehan, was mentioned in Muthu’s blog yesterday.  The work is mentioned in a bullet about problems discussed at a Google research meeting at FCRC and is quoted below (btw was this meeting broadly advertised?  I would have gone if I’d known about it):

  • Big problems, eg., can we provide guidance on how science budget should be allocated among various disciplines, or NSF CS budget among different areas? Given a subset of researchers, say we can estimate their impact on the society when funded. Given this oracle, can we allocate funds to people to maximize social welfare? Can we model people switching teams in second round or open bid systems for reallocating funds? Q: Why doesn’t NSF give $’s to 2 teams for the same project and get them to compete? For some recent work, see the work of Shay Kutten, Ron Lavi and Amitabh Trehan.


It’s a proud and exciting moment to see a former student embark in a research area you know nothing about.  But it’s also a bit disconcerting, like when my 3 year old son beats me at Concentration.

Post Quantum Crypto
August 19, 2010, 4:02 pm
Filed under: Uncategorized | Tags: , ,

My colleague at UNM, Cris Moore, just had his paper on post-quantum crypto slashdotted.  The paper, written with Hang Dinh and Alexander Russel,  shows that a particular type of cryptosystem (the McEliece cryptosystem) resists a particular class of quantum attacks (Quantum Fourier Sampling attacks).  This looks like a nice paper, and maybe a good reason for me to learn more about quantum computation than Shor’s algorithm.

P.S. Belated congratulations also to my freshly minted PhD student Navin Rustagi (former guest-blogger here) who just accepted a post doc with Marek Kimmel at Rice.  A funny story: I first misheard this name as Mark Kimmel, and after googling it (try it yourself) became worried that Navin had been spending too much time in Santa Fe lately…

Opening for PhD student
July 21, 2010, 4:59 pm
Filed under: Uncategorized | Tags: , , ,

This is probably not surprising if you’ve been reading the last several posts on this blog, but I have an opening for a PhD student that I would like to fill soon.  I’m circulating the following announcement about it.

I have one opening for a PhD student with a keen interest in CS theory research and a strong mathematical background to work on a game theoretic project in network security. The project entitled “Beyond Tit-for-Tat: New Techniques for Collaboration in Network Security Games” will focus on how to enable collaboration on the Internet, where populations are highly fluctuating, selfish, and unpredictable. This project will explore a new algorithmic technique for enabling collaboration in network security games which will improve on past approaches such as tit-for-tat in the following ways: (1) it works even in single round games; (2) it works even when the actions of the players of the game are never revealed; (3) it works even in the presence of churn, i.e. players joining and leaving the game.

The position will cover tuition and also pay a stipend of $1,780/month. The position can start in either spring or fall semester of 2011

New Mexico is a hot spot for research in complex systems and interdisciplinary research. The Computer Science department at the University of New Mexico benefits from strong ties with the Santa Fe Institute, and Sandia Labs and Los Alamos Labs. The theory group in our department is particularly strong, having graduated students in the past several years who have performed very well in a challenging job market. Permanent Positions secured by these students include: Asst. Prof. at University of Colorado, Boulder; researcher Sandia Labs; engineer at Microsoft. Post doc positions secured include: University of Waterloo, Technion and University of Victoria.

Interested? Please contact me about the position at: <my last name>

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: