The organizers of IGAFIT 2019 Workshop for Postdoctoral Researchers in Algorithms asked me to share my thoughts on some questions related to the career of postdoctoral researchers in theoretical computer science. So here it comes.

A word of warning might be in order before we begin. I started my own career by studying physics. For seven years. Until I finally realized I don’t like physics and I’m not good at it and then eventually switched to computer science. So my own career probably serves best as an example of what you definitely should not do. But I have also supervised several outstanding postdocs and doctoral students who have made all the right choices with their careers, so I can hopefully give some useful advice, too.

Research and supervision

How to find interesting and approachable research questions?

I usually try to understand simple problems completely.

In his foreword of George Pólya’s How to Solve It, John Conway quotes Pólya saying:

“If you can’t solve a problem, then there is an easier problem you can’t solve: find it.”

This is pretty much what I have been doing throughout my career. I encounter a question that I cannot answer, I make it simpler, and I repeat this process until the problem gets trivial. Then I take one step back and there is a question that is just slightly outside our current understanding. This is what I want to solve.

Eventually, if you manage to solve the simple problems, you will often also get as corollaries answers to more complicated questions — that is, answers to questions other people actually care about. A lot of my own work is on lower bounds, and fortunately there it is enough to show that a problem is hard to solve in some simple special case; then hardness in the general case follows. If you work on upper bounds, just solving a special case may be a bit more difficult to sell to your colleagues…

How to efficiently find interesting not-too-hard open problems, e.g., for supervising theses or for workshops?

Again, my primary recommendation is to look at simplifications. You have a graph problem that nobody has been able to solve? What about special cases: Trees? Bipartite graphs? Regular graphs? Low degrees? Cycles? Grids? Unweighted graphs? Can you relax the problem to make it easier? Fractional relaxations? What about local optima or other equilibriums? Can you look at weaker models of computing to make it easier to prove lower bounds? Can you look at stronger models of computing to make it easier to design algorithms?

I would like to emphasize the importance of gaining understanding of the foundations. Instead of simplifying open problems, many people tend to look at generalizations of problems that have already been solved, but I am not so sure if this is an equally good strategy for finding interesting open problems to study. Given a problem that is solved, there are often many ways to generalize it, and it is not clear why a certain generalization would be particularly interesting or lead to new insights. If it is likely that the end result is merely “the ideas from prior work can be generalized, it just gets complicated and messy”, I tend to avoid it.

How to decide when to stop working on a problem if it is taking too long time?

I am the wrong person to ask this. Our FOCS 2019 paper solved something I had been studying already since 2011 or so, and I am happy I never stopped working on it even if we were getting nowhere. I just keep studying many enough problems in parallel so that there is something where we can make progress. You can revisit your favorite old problem every now and then. And you can always try to simplify the problem to have something you can solve…

How to motivate and encourage students to do research? How to balance between showing them that research can be fun and pushing them to do something they do not care about?

I strongly believe in doing things together. I don’t just give a problem to someone and expect that something good happens. We meet with all kinds of people, talk about research problems, and in general try to have fun solving them together. Show a good example, contribute as much as you can, and everyone else will try to do the same.

How much confidentiality should one maintain on his/her current research?

I tend to share research questions liberally. Our FOCS 2019 paper is again a good example: over the years I talked about this specific research question with all of my colleagues whenever we met, I wrote about the problem in research articles, and I gave presentations about the problem. And this is also how we eventually solved it — we had a meeting with the right set of people, and once again I started to bother everyone with this problem.

But once you have a solution idea in mind, I would recommend keeping some amount of secrecy: work out the details, write up everything quickly, and post on arXiv so that you have a timestamp for your result.

Career and positions

When to start applying for faculty positions? Is it good to go for it early or rather enjoy low administrative burdens of postdoc life longer?

Why wait? Being an assistant professor is also a great way to enjoy low administrative burden…

What’s the longest reasonable time for a postdoc?

Something like 5 years as a postdoc is in my opinion fine. Longer than that starts to get a bit suspicious; having a different job title after that would be good (it does not need to be a professor position).

How much does the name of the place where you do a postdoc count for later?

I think people will be more interested in your publications than places in which you have been at. You can convince me much more easily by talking about your STOC/FOCS papers than by telling me about your job history as a postdoc.

Balance and time management

How much time do you spend on reading papers?

Way too little. Nowadays I tend to accept relevant review requests and committee invitations largely so that I have a good excuse (and a deadline) for reading papers.

Is there a way to reduce / avoid flying (to conferences) without damaging the development of a scientific career?

I tend to avoid conferences that would require long-distance flights. I strongly favor European conferences. I try to minimize long-distance traveling in general. I do not really care that much if it hurts my scientific career; climate and environment are way more important than that. Fortunately, more and more people nowadays understand this.

Others

How to accelerate the dissemination of results and let others know what you do?

Post everything on arXiv. Many people follow arXiv feeds daily.

Make sure you have got an easy-to-find home page that is kept up to date. Make sure you have a Google Scholar profile that is up to date. People will eventually find some papers you have written and get curious about you and other things that you have done; try to make their life as easy as possible.

Cite relevant papers, and their authors will get notifications from Google Scholar.

Be active in social media. Write a blog. There are fairly few people in TCS who are regularly writing blog posts but many people are following TCS blogs, so it would give plenty of extra visibility for your.

Work with lots of people; build a large collaboration network.

What should I do if I want to become a PC member of a theory conference?

Just do good work and publish in relevant conferences regularly and you will eventually start to get invitations. Make sure people who would like to send you an invitations can easily find your current email address.