“You have to have good researchers. Good researchers, all of them.” – Paraphrase of quote from Das Boot.
Sometimes writing a paper can be a challenging slog: goals move as conjectures prove wrong; facts that seem simple turn out to be slippery to prove; experiments must be rerun as the paper evolves; and notation needs to be redone for the sake or readability.
In such a situation, it’s a blessing to have coauthors who will go the extra mile to keep pushing and pushing the paper to completion. So I would now really like to thank my students Jeffrey Knockel and George Saad for their hard work on our latest paper: “Self-Healing of Byzantine Faults” (abstract below, full paper here).
Note: I wouldn’t exactly compare the research process with serving on a U-boat mission during the decline of the Third Reich. For me it’s most similar to mountaineering, whose ethos is captured by the motto of the Seattle mountaineers: “Like fun, only different!”
Paper Abstract:
Recent years have seen significant interest in designing networks that are self-healing in the sense that they can automatically recover from adversarial attack. Previous work shows that it is possible for a network to automatically recover, even when an adversary repeatedly deletes nodes in the network. However, there have not yet been any algorithms that self-heal in the case where an adversary takes over nodes in the network. In this paper, we address this gap.
In particular, we describe a communication network over n nodes that ensures the following properties, even when an adversary controls up to 
PODC 2012 accepted papers are out (and have been for a while). This looks like a great collection of papers, with many focusing on problems in distributed reliability/security. It’s also nice to see some of my former students represented (Maxwell Young and Amitabh Trehan). Some papers that caught my eye:
Adi Akavia, Shafi Goldwasser, and Carmit Hazay
Distributed Public Key Schemes Secure against Continual Leakage
James Aspnes
Faster Randomized Consensus with an Oblivious Adversary
Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip Gibbons
The Cost of Fault-Tolerance in Multi-Party Communication Complexity
Seth Gilbert and Maxwell Young
Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks
Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen
On the Price of Equivocation in Byzantine Agreement
Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues
On the (Limited) Power of Non-Equivocation
Guanfeng Liang and Nitin Vaidya
Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen
Faster than Optimal Snapshots (for a While)
Stephan Holzer and Roger Wattenhofer
Optimal Distributed All Pairs Shortest Paths and Applications
Michael Backes, Fabian Bendun, and Aniket Kate
Brief Announcement: Distributed Cryptography using TrInc
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan
Brief Announcement: Maintaining Large Dense Subgraphs on Dynamic Networks
So here’s one partial solution to the puzzle I described in my last post.
The prover sets up n pairs of cups behind the screen. For pair i, she places X_i stones in both cups, where X_i is a random variable uniformly distributed among the positive integers. Then she removes the screen.
Now the verifier chooses n-1 of the pairs of cups and asks the prover to reveal the contents. The verifier rejects the proof immediately if any of these revealed pairs have unequal numbers of stones.
Next, the prover takes each cup in the unrevealed pair and pours its contents into each of the cups in the original pair of cups in the table. Finally, the prover reveals the new contents of these original cups. If there are the same number of stones in each cup in the pair, the verifier accepts the proof, otherwise, he rejects it.
So this ensures that if the verifier accepts the proof, then the original pair of cups have equal number of stones with probability 1-1/n. Moreover, the verifier learns little about the number of stones in the original pair. It’s not perfect, since the verifier knows, for example, that the original number of stones is no more than the final number of stones. (Of course, if you were doing this on a computer, you’d add the stones modulo some large number)
I’m interested in improvements to this algorithm. Can the original number of stones be better hidden? Can we decrease the probability of error as a function of the number of cups used?
The following puzzle is supposed to have applications in treaty verification.
There are two people playing a game: a prover and a verifier. There is a table between the two people, and on the table are two cups, each with some number of pebbles in them. The prover also has an unlimited supply of cups and pebbles, and a screen she can use to hide activity on her side of the table.
The goal of the game is for the prover to prove to the verifier that the two cups originally on the table have the same number of pebbles in them, but to not reveal the number of pebbles in either of these cups.
How can you ensure that the verifier can be sure that the two original cups have the same number of pebbles with any arbitrarily small probability of error? What is the most efficient protocol you can devise to accomplish this goal? Here efficiency is measured in terms of time (number of rounds) and communication (number of cups), versus the probability with which the verifier can be sure that the two original cups have the same number of pebbles.
The attempt to shut down the Computer Science department at the University of Florida has previously been discussed in the theory blogs (see here and here for example).
I wanted to post a quick update to make sure that the issue remains in the “blogsphere”. This post from saveufcise suggests that the department is still being strongly pressured to merge with EE. You can now take action to help them by either writing a letter or pledging money to create a College of Computing(240K pledged in last 3 days).
I interviewed at U. Florida CISE many years ago, and came away with a very favorable impression of a department that was clearly going places. I can also say that the department is filled with strong researchers (and incidentally nice people), who should not be going through this debacle. This page makes it clear that the CISE department is one of the best in the school of engineering at U. Florida (see excerpts below). So if you can, please take a moment to support them!
“The CISE department at UF has consistently demonstrated its excellence. In 2010, CISE graduated 25 PhD students, (3 times more than that number at 2000). We are bringing 5.5 million per year on research funding, (almost 4 times the amount in 2000). We have 2 ACM Fellows,4 IEEE Fellows and 2 AAAS Fellows; many faculty have won other awards and are on prestigious editorial boards and program committeees. Almost all have active NSF or NIH funded research programs. 12 young faculty won NSF Career Awards, which is 22% of College total, (also 5 times more than 2000). Over the last 5 years, we have won 11 best paper awards. we teach thousands of nonmajors, and approximately 600 undergraduate majors, 400 masters and 131 PhD’s with 32 tenure track faculty and at this moment, only 3 nontenure track faculty! CISE is generating 17% of the college’s primary source of income (weighted student credit hours) while only costing only 10% of the college. The Dean herself admitted during her Apr. 12 interview with students that the CISE department has the highest revenue/cost ratio in the college. CISE faculty are actively collaborating with researchers in almost every UF College, along with many national and international universities, as befits the flagship research institution of the state.
It is impossible to overemphasize the importance of a strong Computer Science and Engineering program in today’s economy. The predicted growth rate for Computer Science positions over the next ten years is 30%, almost 3 times the predicted growth rate for all engineering occupations. Software engineering jobs have consistently achieved high national rankings (#1 in 2011 and 2012).
Gainesville’s technology job sector has exploded in the last three years, with the founding of companies such as Grooveshark, Infinite Energy, and Shadow Learning. MindTree recently selected Gainesville as the site for its US expansion largely due to the presence of the CISE program. The opening of the UF Innovation Hub on January 11th promises to draw even more high-tech companies to Gainesville.”
A nice article on how colonies of cells make decisions. Insight into how to control these decisions might help prevent bacteria from deciding their number are large enough to start an infection or create a biofilm…
[HT to Peter Robinson and Amitabh Trehan]
[This is a guest post by my former PhD student Amitabh Trehan. Amitabh is now finishing up a post doc at Technion and rumor has it that he's been giving job talks at some of the IIT branches in India (The IITs are like the MITs of India) - Ed]
Matt Damon was a genius janitor solving math problems posted on blackboards in ‘Good Will Hunting’ – I wonder how his character would have done in ‘Job Ville Hunting’!
Well, returning to the reality of us more mortal types, there comes a stage when every PhD student needs to go where they’ve been postponing going before – Jobville. Having been through the process in the recent years and still actively driving around in Jobville, I thought I will summarize my thoughts. I will mostly skip the details of failed attempts, missed deadlines and numerous faux pas in the favor of some well distilled advice. I suppose this will be most useful for students looking for postdoc positions and a career in academia, but some of the advice maybe generally useful too.
What has worked for me so far could be called a social networking approach, though I will not say that I had planned it such. In other words, there may not be a single approach which may work for all, but the bottom line is that if you do good work and you let people know you are a promising candidate, they may open the doors for you. I consider myself fairly lucky in the opportunities I have been given and the appreciation I have received for my work. Here are some tips.
What works? Personal interaction counts. Be ready to talk, present and travel. If you plan to be in academia, this is going to be the major portion of your professional life anyway. So, start early – meeting people, talking and presenting your work not only helps setup future collaborations and gets people interested in working with you, it may interest them to have you as a postdoc or a faculty closer to their own place of work. Research is an increasingly collaborative venture and even in the age of skype, physical distance counts. But, remember to be enthusiastic and organized. There is another rule of thumb : if interested, send an email. This works for almost anybody in any part of the world, for any job. However, be sincere when you send that mail; do not spam. After all, an academic career is built on reputation.
Now, for some more technical details 
Start early: Yes, yes, we’ve been conditioned to procastinate and that’s why this is even more important. The process takes much longer than you would imagine, so start early. Of course, it’s entirely possible it may not take much time for you to get a postdoc offer (the faculty process may involve more formalities) but even that would happen when you advertise that you are ready. The time you want to start with your warmup exercises also depends on which part of the world you are interested in going (see the next point). I would suggest getting serious about the process in the summer before the year you plan to be in the market.
Know the global market and application cycles: Less than a decade ago, I had heard that as a CS PhD, you don’t even need a postdoc to be offered a faculty position. That seems to have changed in a hurry. A friend mentioned to me that if somebody had told him finding a faculty postion post PhD would be so tough, he may have settled for a MS and a job in the software industry.
The academic market is now closely related to the global economic conditions as witnessed by the slowdown in the US economy. You may be interested in exploring globally e.g. Europe, Singapore, India. However, different countries have different applications cycles, application rules and procedures (some of which can be pretty frustrating). For example, a postdoc in Israel may be required to start in October (September is the holiday month there) but the positions may be finalized as early as February or March. Similarly, the faculty position openings in the US start advertising in the winter of the previous year whereas in India they may start around March of the year. I also heard the following: In some places (this was in Europe), you may need three independent referees to certify that the place you claimed to have done your PhD from really exists (and the person who endured this is from MIT).
Try to do good work: Though this goes without saying, researchers face a dilemma: quality or quantity? Is ‘publish or perish’ here to stay? A fellow applicant pointed out that it seems that some applicants now have as many papers as seasoned researchers of the past have over their career. However, if you have a few publications in high quality conferences and journals, it is likely to count much more than a host of medium level publications.
Get your thoughts together i.e. the research statement: Very important. Each time you write your research statement, you discover a lot about yourself and your research, even if you discovered a lot about yourself last year! This is another of the items that seems to take forever to write: It seems you should be done tomorrow, but you will remember that you had felt the same a month ago! You also have to maintain a polished CV and teaching statement.
Join mailing lists and websites: You need a source to discover new openings. There are some good resources on the Internet: www.cra.org is a great resource – they have a very useful mailing list called CRA job openings. http://www.mathjobs.org/jobs is another useful place for Computer Scientists – in fact, you can apply through here for many positions using the same set of basic documents (CV, research statement, teaching statement etc).
So, if you are ready to embark on an adventure in jobville, all the best, and remember to try to solve any problems you see written on blackboards! (I am usually too lazy to do that, but you should give it a try
There’s a nice article on Eric Demaine’s work on origami in Nature recently, along with some beautiful pictures. I like the fact that it’s probably the only article in Nature that has ever contained the phrase “balloon animals”.
There is a nice set of articles on Alan Turing in Nature this month, in celebration of his 100th birthday. This short article “The Man Behind the Machine” is a good place to start. Much of the short article will be familiar to computer scientists, but there’s a funny bit about umlauts being initially added to his name in the phrase “Turing Machine”, “due, presumably, to an impression that anything so incomprehensible must be Teutonic”. Also there’s an interesting later article on Turing’s biological work on morphogenesis.
