Q&A

1. What led you to academia?

Much to the shock of my fellow students, I have wanted to be a professor since my freshman year in Italy. The pursuit of knowledge and the lifestyle freedom really appealed to me. Naturally, I did not have a clue; but I would do it all over again, changing nothing… alright, almost nothing.

1. How did you become interested in theoretical computer science?

I was totally hooked to computers since I was eight, and also worked on videogames in my early teens. In high school I didn’t mind math, but it was not my passion: It was mostly calculus which I thought was “only good for physics.” In college I had a first glimpse of theoretical computer science, and I was struck. The field was asking the right questions: What is a proof, what is knowledge, what is randomness, when you are short on time?

1. What are you currently working on?

The most famous open problem in the field is the P vs. NP problem which can be phrased as asking to prove that Super Mario levels, properly constructed, are hard to beat. The general challenge is to exhibit problems that require a lot of time on computers. Much of my research concerns proving such limitations for restricted models of computers, for example computers with no memory. Even understanding such restricted models has proved enormously difficult, and a good reason for that is that they are extremely powerful, much more so than anyone anticipated.