The Simons Institute in Berkeley will hold a conference on “visions of theory of computing” during May 29-31, 2013 (just before STOC):
This three-day symposium will bring together distinguished speakers and participants from the Bay Area and all over the world to celebrate both the excitement of fundamental research on the Theory of Computing, and the accomplishments and promise of computational research in effecting progress in other sciences — the two pillars of the Institute’s research agenda.
Lots of interesting speakers.
Posted in Uncategorized | Leave a Comment »
A summer school on Matching Problems, Markets, and Mechanisms will be held in Budapest on June 24-28, 2013; see the website for more details. Incidentally, the summer school will be followed by the Erdos Centennial conference.
Posted in Uncategorized | 1 Comment »
I turns out that Paul Erdos was born 100 years ago today. Nowadays his name most often comes up in the context of people’s Erdos numbers, so this happy occasion seems like a good opportunity for two anecdotes.
Anecdote 1. The Bacon number is the distance from Kevin Bacon in the graph where vertices are actors and there is an edge between two actors if they played in the same film. There is also an Erdos-Bacon number, which is the sum of one’s Erdos and Bacon numbers. I once read that Erdos had a Bacon number of 3, which would give him an astounding Erdos-Bacon number of 3; but this is false. Wikipedia tells the story:
He [Erdos] appears in N Is a Number: A Portrait of Paul Erdos (1993) with a Gene Patterson, and a Gene Patterson was in Box of Moon Light (1996) with Sam Rockwell who was in Frost/Nixon (2008) with Kevin Bacon. However, this is incorrect, as the Gene Patterson in N Is a Number: A Portrait of Paul Erdos is not the same person as the one in Box of Moon Light (1996).
According to the Wikipedia article Natalie Portman, Carl Sagan, and Richard Feynman have Erdos-Bacon numbers of 6.
Anecdote 2. My PhD advisor Jeff Rosenschein has an Erdos number of 3, so when I published my first paper with him my number decreased from infinity to 4. A year or two later, I wrote a paper with Bezalel Peleg, who has an Erdos number of 2, and we submitted it as a technical report. At this point I started bragging that my Erdos number is now 3. My office mate Shahar Dobzinski (whose own number is 3, I think) was quick to point out though that a technical report doesn’t count for the purposes of computing one’s Erdos number. Of course we turned to Wikipedia to adjudicate this important dispute. Wikipedia (still) says that the Erdos number is “measured by authorship of mathematical papers”. My paper with Bezalel is clearly a mathematical paper, right? Shahar wouldn’t give up, and looked up the definition of a “mathematical paper”. I couldn’t find the relevant entry now (this was six years ago), but if I remember correctly the (somewhat circular) definition that Shahar was able to find was that a mathematical paper is published in a “mathematical journal”. I was defeated.
Eventually I published a few papers with Noga Alon — whose Erdos number is 1 — including one in the journal Mathematics of Operations Research and one in the journal Discrete Mathematics. Journals with the word “mathematics” in their names are clearly mathematical journals, right?
Posted in Uncategorized | 6 Comments »
The Second Cambridge Area Economics and Computation Day (CAEC’13) will take place in Cambridge (the one near Boston) on Friday April 26th. It will include long talks by Daron Acemoglu, Yiling Chen, Matthew Jackson, and (recent Turing Award winner) Silvio Micali, as well as short talks and posters (for which you may send an email to email@example.com by Thursday April 11, 2013.)
Posted in Uncategorized | 2 Comments »
Over a recent lunch, Boris Bukh suggested the following variant of the Turing test: a human and a computer play a game (in the game-theoretic sense). A judge who is observing only their moves must decide with confidence who is the human and who is the computer. The premise is that the human would play irrationally (he’s just a random person off the street), and the computer’s goal is to also play irrationally to avoid detection.
An interesting aspect of the economic Turing test is that it’s not clear whether it’s harder to be the judge or the computer (programmer). On the one hand, how do you program a computer to act irrationally? On the other hand, if a judge has a set of rules that identify humanly irrational behavior (e.g., he read the papers of Kahneman and Tversky), couldn’t the programmer implement the same set of rules?
I found this idea especially appealing because I sometimes think of rationality as a possible key to artificial intelligence. Indeed, one can argue that rationality is perceived as (a sufficient condition for) intelligence, and therefore a multiagent system that is based on game-theoretic principles will be perceived as intelligent, so in that sense game theory can enable classic artificial intelligence (albeit on the multiagent level). The economic Turing test turns this argument on its head: to be indistinguishable from a human the computer must strive to be irrational.
The field of AI has so far failed to deliver human-level intelligence; is this the dawn of the age of artificial stupidity?
Posted in Uncategorized | 7 Comments »
I recently read this nice blog post about doing a PhD by CMU’s Dave Andersen (who, not surprisingly, rather enjoyed his PhD), and it inspired me to share a PhD-related memory of my own.
When I finished my PhD at the Hebrew University of Jerusalem, I was asked by the powers that be to give a short speech on behalf of the new graduates at the university’s graduation ceremony. To help me prepare the speech they sent me the previous year’s speech, which I read in disbelief. Here is a translation of a paragraph from that speech:
During this period [of doing a PhD] it became clear to each one of us that writing a thesis is more than an academic endeavor, it is a test of character; a psychological rather than purely intellectual challenge. It is akin to the loneliness of the long-distance runner. Each small step seems inconsequential compared to the long way that must be traveled, but in retrospect every step, even if it seemed to be in the wrong direction, gets you closer to the finish line.
Other parts of the speech cite Freud and Goethe so I don’t think this person is a computer scientist. When I read this I almost lost my nerve though. After all, I enjoyed every minute of my PhD; but wouldn’t the philosophy graduates lynch me if I said so? Ultimately I decided to give the speech and admit how shamefully enjoyable those four years were. Although I didn’t use notes for the real thing, I had to submit a draft for approval, so I still have a version that’s presumably similar to what I actually said. Here’s a translation of the first and last paragraphs:
I recently read online a story about what is supposedly the most desirable job in the world: Protecting a coral reef in Australia while documenting your experiences in a blog. If memory serves, some forty thousand people competed for the job, and ultimately a lucky British guy got it. When I read that I thought to myself: they’re wrong, there is a better job: doing a PhD… and I’m saying this without a drop of cynicism. Which other job gives you absolute freedom to do the things that you find most interesting and work with some of the smartest people in the world, and at the same time there are almost no requirements and duties? [Well, this is true in Israel, not at CMU...] It is truly a wonderful thing if your goal in life is not to get rich.
[Two paragraphs about how awesome the Hebrew University is, thanking our parents, etc... ]
Personally I enjoyed every minute of this experience, which lasted a few years, but all good things must come to an end. Fortunately, the consensus among academics is that there is only one job that is better than doing a PhD: doing a postdoc!
Posted in Uncategorized | 1 Comment »
The Nevanlinna Prize committee is seeking nominations for the 2014 award (to be sent to the chair). The prize recognizes a researcher under 40 years old for work in “All mathematical aspects of computer science”.
Posted in Uncategorized | 1 Comment »