My student Abhinav Aggarwal has just written the inaugural post on his new blog (the name of which, I hope, is not a comment on the soporific qualities of my advisement 🙂 His first post is on the Clever algorithm by Jon Kleinberg. This is inarguably, the paper that started the modern, spectral-based approach to web search that Google has built on so successfully.
Some questions worth pondering while reading through Abhinav’s summary (and hopefully also the seminal paper itself): 1) Why did PageRank “beat out” the Clever algorithm in real-world web search? 2) Are there domains besides web search where one might use a “top left and right eigenvector” approach like the Clever algorithm? 3) What about the “soft” results in the paper like the use of the second eigenvector for clustering? Can these be formalized in an interesting way?
Filed under: Uncategorized | Tags: distributed computing, students, theory
Congratulations to Mahnush Movahedi who today just passed with distinction her dissertation defense on Efficient and Robust Distributed Computing. Serving on her dissertation committee were Sean Luan (UNM), David Evans (UVA) and Maxwell Young (MSU). After graduation, Mahnush will be will be moving to the University of Virginia as a postdoc to work with David Evans on Secure Computation.
It’s a great pleasure to have worked with Mahnush! She and Mahdi will both be greatly missed in our research group.
Filed under: Uncategorized | Tags: distributed computing, students, theory
Congratulations to Mahdi Zamani who just passed with distinction his
dissertation defense on “Scalable and Robust Algorithms for Privacy-Preserving Applications”. After graduation, Mahdi will be will be moving to Yale CS as a Postdoc to work with Joan Feigenbaum and Bryan Ford on the Dissent Project. Serving on his dissertation committee were Jed Crandall, Trilce Estrada and Brian Ford(EPFL).
It’s a great pleasure to have worked with Mahdi and he’ll really be missed in both our own research group and at UNM.
Congratulations to Dr. George Saad who just defended his dissertation (with distinction) yesterday on “Selfishness and Malice in Distributed Systems”. George’s dissertation focused on designing 1) algorithms for self-healing in networks with Byzantine nodes and 2) designing mediators to improve social welfare in a type of El-Farol game with both positive and negative networks effects. Here are slides from his excellent talk.
George will be taking a position at the Silicon Valley startup Jasper Technologies next month. On his committee were Maxwell Young (Drexel University), Tom Hayes and Dorian Arnold.
Congratulations George!
Filed under: Uncategorized | Tags: distributed computing, students, theory
A quick pointer to an interview with my former student Amitabh Trehan on his DISC paper “Dense Subgraphs on Dynamic Networks” .
This is a neat result in the dynamic graph setting where an adversary can add and delete edges in a graph, but the number of nodes is always fixed at n. One of their results is as follows. In the case where the maximum number of rounds that it takes a message to traverse the network is always polylog, they give a polylog time algorithm that allows each node to approximate within a constant factor the densest subgraph. This is in the CONGEST model where in each round, each node can send an O(log n) bit message to each neighbor.
Congratulations to my student Olumuyiwa (“M”) Oluwasanmi who successfully defended his dissertation on “Practical, Scalable Algorithms for Byzantine agreement” last week!
Usually on this blog, I allow only a 1 slide dissertation summary, but today I’m making an exception for 2 slides (at least they have the same x-axis :). The slides below summarize the performance of 4 Byzantine agreement algorithms. The CKS algorithm is from the paper “Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography“. The remaining 3 algorithms are from M’s dissertation, and the algorithms with the RB prefix assume the existence of a random beacon.
Congratulations to Dr. Maxwell Young who successfully defended his dissertation on Resource-Efficient Communication in the Presence of Adversaries at the University of Waterloo yesterday. Max got his Masters degree with me at UNM way back when I first started as a faculty member, and he was the very first student with whom I published a paper. He’s hard-working, talented, and also a lot of fun to work with. One of the great pleasures of academia is seeing student develop as researchers, and then have the possibility to continue to work with them as colleagues. Max and I have been actively working together for many years now, and I’m looking forward to visiting him in Singapore during his post doc with Seth Gilbert next year.
Congratulations Max!!!
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.
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…
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>@cs.unm.edu
Machinations 