Faculty and postdoc positions at EPFL

2012 November 13
Comments Off
by Aleksander

EPFL has a CS faculty search and theory (especially, complexity, crypto, or algorithmic game theory) is one of the priority areas. The ad can be found here:

Also, EPFL theory group has a postdoc opening. More at: http://theory.epfl.ch/osven/postdoc.html

“Algorithmic Frontiers” Workshop – Student Support Deadline

2012 April 9
Comments Off
by Aleksander

Just a quick reminder:

The deadline for applying for financial support to attend the “Algorithmic Frontiers” workshop is April 15.

More details: http://frontiers.epfl.ch

Getting the “Big Picture” – Algorithmic Frontiers Workshop, June 11-14, 2012 – EPFL

2012 February 4
by Aleksander

One of the things that really drew me to theoretical computer science was its “compactness”. Namely, even though I don’t think it is possible anymore to be an expert in all the areas of theory, one is still able to get a general grasp of what each of these areas is about, what kind of tools it employs and where it is headed. I think this is a real strength of our community and we should try to cultivate it as our field grows both in breadth and depth.

Therefore, I am a bit concerned that – with a notable exception of the last year’s workshop in Princeton – I am not really aware of any forum that aims at reinforcing this kind of “big picture” view of theory. (Apparently, our conferences used to serve this purpose, but I have my doubts they do anymore.)

Because of that, I’ve always wanted to have a theory workshop that employs a bit different approach to choosing its program than the usual workshops do. (Not that there is anything wrong with the usual workshops – they just serve a different purpose!) Namely, instead of choosing some very specific research area or question and then soliciting talks that relate to it,  I would like it to simply choose a set of interesting speakers and ask them to give an accessible, big-picture presentation on research area or question of their choice – without any real restrictions on the scope or the character of their talk. In contrast to the traditional workshops that cater exclusively to experts in a specific area, the goal of this event would be to expose the audience to a variety of topics that they know very little about and probably would not stumble upon otherwise. From my experience, such a random tour is a great way to both get a general grasp of various areas of theory, as well as, discover connections between them.

Now, after entertaining the above idea for quite some time, I finally have an opportunity to implement it!

Below you can find an announcement of a workshop that my colleagues Christoph Koch, Rüdiger Urbanke and I are organizing this summer at EPFL.

Algorithmic Frontiers Workshop
June 11-14, 2012, EPFL, Lausanne

The goal of this workshop is to bring together experts from across various areas of algorithms and optimization to share their perspective on problems, tools, and/or results that they find important. Our intention is to provide the attendees with a bird’s-eye view of what are some of the exciting developments, important directions, and key obstacles to further understanding of algorithms today, as well as, provide a forum for discussion of possible new approaches to existing challenges.


Alexandr Andoni (MSR Silicon Valley)
Sanjeev Arora (Princeton University)
Michel Goemans (MIT)
Elad Hazan (Technion)
Piotr Indyk (MIT)
Satyen Kale (IBM Research)
Sanjeev Khanna (University of Pennsylvania)
Robert Krauthgamer (Weizmann Institute)
Lap Chi Lau (CUHK)
Gary Miller (CMU)
Mihai Pătraşcu (AT&T Labs)
R. Ravi (CMU)
Dan Spielman (Yale University)
David Steurer (MSR New England/Cornell University)
Santosh Vempala (Georgia Tech)
Nisheeth Vishnoi (MSR India)
Jan Vondrák (IBM Research)
Uri Zwick (Tel Aviv University)

More information:


As you can see, we managed to get a terrific set of speakers and I am really excited to see their talks.

Hope to see you in Lausanne in June!

We Are Hiring

2011 December 3
by Aleksander

In addition to the theory postdoc positions I mentioned previously (see here), EPFL will be hiring in CS this season (you can find the ad here). Theoretical computer science is one of the preferred areas, so theory candidates are encouraged to apply.

Now, once the official announcement is over, let me confess that I was relatively clueless about EPFL at the time I applied for the position – I heard some intriguingly good things about the place, but that was it (and, obviously, the official hiring ad was not too informative, either). It was only during and after the interview that I learned more.

So, to not put you in the same situation, let me say a couple of words about EPFL – hopefully, it will give you some better perspective.

For over a decade now, i.e., since appointing Patrick Aebischer as its president, EPFL has been going through a period of very rapid growth and changes. These changes are inspired by the way top US universities are being run and, among other things, resulted in introducing a true tenure-track system.

From the perspective of the school I am in (as EPFL is relatively small, it has a very flat structure and there is no real departments – only schools), last decade involved, in particular, a long string of hires – mostly in systems-related areas – of absolutely top-notch people. (Some of them were coming from tenured positions at places like Berkeley, CMU, or Cornell.) As a result, the school has now a very strong presence in many aspects of CS systems, as well as, in information and coding theory. Thus, as you might guess, the current focus is on building up a similar strength in the remaining areas of CS, mostly theory and machine learning.

Now, from the point of view of a (junior) EPFL professor, I must say that so far things seem to be not too different from what I would expect at a US university. (I guess that given that the president of EPFL, the dean of my school, and a significant fraction of the school’s faculty have spent big chunks of their careers in the US academic system, I should not be too surprised.)

The only real difference that I have experienced thus far is a significantly better funding situation. The school is able to provide the faculty with enough funds (on annual basis) that one does not feel the pressure of grant-chasing. (At least, if one is a theorist whose only real expenses are students, postdocs, traveling and pencils/paper laptops.) Needless to say, spending large part of my time and energy on convincing people that they should fund my research, is something I can happily do without.

Also, one more thing about EPFL that I feel is worth mentioning is that it has a bit of a start-up-like atmosphere. Namely, there is some interesting mix of enthusiasm, energy, constructive criticism and can-do attitude around this place that makes you simply enjoy putting ideas into action (hopefully, more on some of these ideas soon).

So, I hope that the above gives you some better idea on what kind of university EPFL is, as well as, on what were some of the reasons why I decided to be a faculty there. There are some more things one should probably discuss here, but I am afraid that my post is too long already. Maybe I will come back to this topic sometime in the future.

In any case, I wish you all good luck with your applications! Wherever you are applying to :)

Changes, Changes, Changes…

2011 November 24
by Aleksander

Well, it has been a while since my last venture into the blogosphere. I guess it has been almost a year now.

As you might imagine, there were reasons for that. Being on the job market and then writing up the thesis, all of this on top of the usual work schedule and family life…you get the idea.

This hectic period resulted in quite a few changes in my life. After graduation, I moved a few blocks down the street to become a postdoc at Microsoft Research New England and now I am greatly enjoying my time there.

However, an even bigger change (and move) is about to happen next year. Starting Fall 2012, I will be a faculty member at EPFL.

To be honest, this is a bit of a surprise even to me. I was always playing with a thought of going back to Europe at some point, but I was imagining it would happen a bit later in my life. However, once I got to know EPFL and the people there, I knew what my decision will be. It is a place with true drive towards excellence and a lot of success on this front already.  So, given its potential and commitment to further growth,  it was clear to me that this is one of these big opportunities that – even though there is a chance it will not work out – you simply cannot pass up.

As a result, in less than a year I transitioned from a student looking for postdoc and faculty positions to a faculty member who is actually looking for students and postdocs (see the info here and here). Should be an exciting challenge!

P.S. Happy Thanksgiving!

STOC 2010 accepted papers

2010 February 9
by Aleksander

FYI: STOC accepted papers are up.

Applying to grad school – some Frequently Asked (but not frequently answered) Question

2009 December 15
by Aleksander

My first experience with US academic culture was applying to grad schools. For me, this process not only involved a lot of anxiety (which I guess is pretty common and to be expected), but also real confusion about how my application should look like, and how the whole process really works. The latter was caused by the fact that I didn’t know anyone who has been a grad student in the US (or even an undergrad student for that matter) in any discipline, so all my knowledge was based on very scarce resources available on the net (I think I found this document by Mor Harchol-Balter quite enlightening), and a couple of helpful tips I got by emailing some polish MIT students. In the light of this, the fact that – in the end – I did reasonably well, I attribute entirely to stroke of luck and unwavering faith of my professors in me.

However, despite this happy end,  I don’t think that feeling clueless is the best state of mind to be in while applying. Therefore, I would like to try to answer a couple of most common question that I either was asking myself, or am being asked by people going through application process now. The list of these questions is by no means exhaustive, so feel free to ask in the comments if some question of your interest was not addressed. Also, keep in mind the following:

Disclaimer: As knowledgeable as I might appear, I have absolutely no experience in conducting any actual admission process.  All my answers are based on my personal experience of being an applicant, and my guesses on how the whole process works. So, take my advice with a healthy grain of salt, and feel free to disagree with it in the comments :)

Q:What constitutes a perfect application?

The main (if not the only) quality in the candidates that the admission committees (at least at all top research universities) is looking for is research potential. So, an application of a ‘perfect candidate’ should  indicate exactly that he will be motivated and successful researcher. Unfortunately, as elegant as the above sounds, no one ever really succeeded in finding an always-working algorithm measuring this potential. For any benchmark people could come up with (e.g. academic performance, prior research experience) there were always examples (this being probably the most famous one) that made them fail. Of course, this doesn’t mean that there is no benchmark that have some significant prediction power — but the fact that there is no single objective criterion results in admission being an inherently noisy and subjective process. Therefore, despite the effort of the admissions committees to make as good job as possible, in the end, the evaluation of your application depends crucially on the personal views of the reviewing professors on what are the good indicators of you being a good researcher in the future.

The above should not of course scare you off,  just keep in mind that the admission decisions are not really an absolute evaluation of you as a future researcher — e.g. I know very strong candidates  that weren’t admitted to all the schools they applied to, even if they turned out to be very successful during they grad studies. So,  to alleviate the above problems, you should focus on making your application as good as possible, and reduce the noise by applying to more than one university.

Q: So, what are the most important parts of the application?

The whole application draws a picture of you as a prospective student — from your academic performance, through the research that you might have already done, to the glimpse of your personality in the personal statement. But still, I would brave a thesis that there is one and only one part of your application that really matters: recommendation letters.

What is the rationale for this? Well, as I said, no one really knows what is the best way to evaluate your potential as a future researcher. However, the general consensus is that it is  not just a function of easily measurable things like your academic stats (your GPA, GRE, number of classes taken in the undergrad etc.), or how well you wrote your personal statement. So, what one does in the case when one has to evaluate a candidate anyway? One just asks for an opinion of another researcher that knows you better and had opportunity to see you thinking, solving problems, and doing all the stuff that is tangential to what you will do as a successful grad student! Therefore, it is no wonder that the admission committee will spend most of its time reading what is (and what is not) in the recommendation letters, and only glances over the rest of your application materials.

Q: …but what about personal statement?!

Yes, I know how you feel now – you spent countless hours agonizing over every sentence in your personal statement, you rewrote it a couple of times, made it as witty and shiny as possible, and now I tell you that it does not matter?!

Well, not quite. What I said is that your personal statement does not affect too much the admission decision (unless you screw it up badly :). However, it still serves the purpose of not only giving some personal touch to your application, but also conveying some important information. For instance, it might indicate what are the areas of tcs that you already explored and found interesting, as well as, what the areas you find intriguing and think about exploring, or even working in, in the future. Also, it might be a good idea to mention professors in the given school you would be excited to interact with. The above information is by any means treated as any kind of commitment on your side to what and with whom you will be working on if admitted (after all, at this point you simply don’t have enough information to judge such things). But they are still useful to admission committee, since they can for instance  forward your application to a particular faculty member that they think might find your application interesting. (Of course, you should not overdo it by saying that you are extremely excited about interacting with all the faculty members and work in all the areas.)

The important thing is to keep your statement concise, and make it have some easy to recognize structure, so as to committee members can easily locate the parts they are interested in (and skip the ones they are not).

Q:Who should I ask to write my recommendation letters?

Well, unless you are lucky enough to have some not-only-classroom interaction with many professors, usually the choice of recommendation letter writers is pretty natural. But, just for the sake of completeness, there are two main criterion that you should consider when choosing your letter writers:

  1. Does this person know me well and has good opinion of me?
  2. Will this person be known (or at least credible) to the people reading these letters?

Clearly, the first criterion is more important — if the person does not know you, or does not have very good opinion of you, then no matter how credible this person is, she/he will not be able to write anything more than some mildly positive things about you (and in the world of recommendation letter, mildly positive letter means a  bad letter). On the other hand, having absolutely enthusiastic letter from your classmate, does not really  carry too much weight.

The general rule of thumb is to shoot for, at least one, as senior and well-know person as possible (if, of course, you have some reason to believe that this person satisfies criterion 1.), and at least one person that is maybe not very senior, but really knows you (e.g. worked closely with you), and has very good opinion of you.

Keep in mind that it is harder to get a very strong letter from a more senior person, since they have seen more and are harder to impress (but if you can get one, more power to you!). And usually,  if you politely ask whether a person could write you a letter, they will give you a hint whether they think they can write a good recommendation letter for you.

Q:I have no publications, should I be worried?

Definitely having some publications (even in some related field, and not necessarily in top conferences) is a desirable thing, since it indicates that you have some concrete research experience — which hints at having research potential — and probably some of the people you conducted this research with, might be good candidates for writing your recommendation letters (see above). However, having said that I know quite a large number of people who are very successful with their grad school application without having a single publication. (Of course, in this case these people have some other factors that convince the admission committee that they have research potential.)

So, if you have some publications – good for you, if not – it does not, by any means, imply lack of success in applying: you could for instance have strong recommendation letters based on impressive interaction with some faculty members at your undergrad institution, even if this interaction did not end up in publishing anything.

Q:I am not from a top school, do I have any chances?

Indeed a large fraction of successful applicants come from the top undergrad institutions. Being at such institutions helps you in many ways. For example, all the potential letter writers that you will get there will probably satisfy criterion 2. above. Also, at such schools you usually get quite early on some hands-on experience in doing research, which quite often results in some very good publication record at the time of applying, and — needless to say — this is helpful. One — relatively small, but still – downside of being in a top school,  is that it is really hard to obtain strong recommendation letters, simply because a lot of your classmates are exceptional too, and it takes a lot of work to impress some professor (but again, once you achieve this, it makes a very strong application).

So, I cannot deny that coming from top school is helpful, but it is definitely not a decisive factor in your application’s evaluation: each year, even top schools admit a significant number of students (including myself) that come from a bit less prestigious or well-known universities. Thus, don’t worry that your application will be trashed without consideration the moment they see you are not from a top undergrad institution.

Q:Is knowing some professors in the department I am applying to needed to be admitted?

If you know this professor well (and she/he has good opinion of you) then it helps (as always), but it would be unreasonable to require that you should know someone. So, don’t worry.

What you should not do, as tempting as it is, is emailing any professor, during or prior the admission process, in order to ask him about your chances of getting in, his willingness to advise you, or just to ‘get noticed’. In the worst case, you will actually get noticed, but tagged as an annoying person that does not read the ‘please read before emailing me’ sections on faculty’s webpages.

Q:So, what is the magical trick that gets you in?

Well, if there is some magical trick then I unfortunately don’t know it. It seems that actually during your senior year you don’t have too much impact anymore on the success of your application (well, at least you can’t impact it in positive way :) So, all I can say is work hard, enjoy what you do, and the things will work out just fine!

As you probably know better than I do, deadlines for grad school application are very soon. So, wrap up your personal statements, fill out all the sections of the applications form, and GOOD LUCK!

Hello World! What it will all be about?

2009 November 30
by Aleksander

Today is the first day of the existence of my blog! I’ve been thinking about creating one, since I settled down at MIT.  The reason for doing this was to present the research I find interesting, and to share with you my experience of  grad studies in the US, and of the community around theoretical computer science.

In particular, doing research in both Europe and the United States, as well as, having contact with various areas of computer science, mathematics, and physics, made me aware of  the existence of such a phenomenon as research culture. Similar things tend to be done differently when approached by mathematicians, physicists or computer scientists. There is even a significant difference in the way they’re done in Europe versus in the United States.

In fact, I noticed that this research culture affects almost all aspects of our academic life. From the way we select the problems to work on, through our choice of tools we employ in our investigation, to the way we evaluate the importance and beauty of the obtained results. However, despite the significance of this culture, it seems that we rarely discuss it as a community. Therefore, in this blog I would like to share with you my grad student’s experience of theoretical computer science seen not only as a collection of publications, but also as a community and culture.

So, stay tuned, and I hope you will enjoy it!