You are currently browsing the category archive for the ‘politics’ category.

Click for full size

Oh man, not another election! Why do we have to choose our leaders? Isn’t that what we have the Supreme Court for?
– Homer Simpson

Nate Silver is now putting Barak Obama’s chance of reelection at around 85%, and he has been on the receiving end of considerable criticism from supporters of Mitt Romney. Some have criticized his statistical analysis by pointing out that he has a soft voice and he is not fat (wait, what? read for yourself – presumably the point is that Silver is gay and that gay people cannot be trusted with such manly pursuits as statistics), but the main point seems to be: if Romney wins the election then Silver and his models are completely discredited. (E.g. here.) This is like someone saying that a die has approximately a 83% probability of not turning a 2, and others saying, if I roll a die and it turns a 2, this whole “probability” thing that you speak of is discredited.

But still, when someone offers predictions in terms of probability, rather than simply stating that a certain outcome is more likely, how can we evaluate the quality of such predictions?

In the following let us assume that we have a sequence of binary events, and that each event $i$ has a probability $p_i$ of occurring as a $1$ and $1-p_i$ of occurring as $0$. A predictor gives out predicted probabilities $q_i$, and then events $E_i$ happen. Now what? How would we score the predictions? Equivalently, how would we fairly compensate the predictor?

A simple way to “score” the prediction is to say that for each event we have a “penalty” that is $|E_i - p_i|$, or a score that is $1- |E_i - p_i|$. For example, the prediction that the correct event happens with 100% probability gets a score of 1, but the prediction that the correct event happens with 85% probability gets a score of .85.

Unfortunately this scoring system is not “truthful,” that is, it does not encourage the predictor to tell us the true probabilities. For example suppose that a predictor has computed the probability of an event as 85% and is very confident in the accuracy of the model. Then, if he publishes the accurate prediction he is going to get a score of .85 with probability .85 and a score .15 with probability .15. So he is worse off than if he had published the prediction of the event happening with probability 100%, in which case the expected score is .85. In general, the scheme makes it always advantageous to round the probability to 0% or 100%.

Is there a truthful scoring system? I am not sure what the answer is.

If one is scoring multiple predictions of independent events, one can look at all the cases in which the prediction was, say, in the range of 80% to 90%, and see if indeed the event happened, say, a fraction between 75% and 95% of the times, and so on.

One disadvantage of this approach is that it seems to require a discretization of the probabilities, which seems like an arbitrary choice and one that could affect the final score quite substantially. Is there a more elegant way to score multiple independent events without resorting to discretization? Can it be proved to be truthful?

Another observation is that such an approach is still not entirely truthful if it is applied to events that happen sequentially. Indeed, suppose that we have a series of, say, 10 events for which we predicted a 60% probability of a 1, and the event 1 happened 7 out of 10 times. Now we have to make a prediction of a new event, for which our model predicts a 10% probability. We may then want to publish a 60% prediction, because this will help even out the “bucket” of 60% predictions.

I don’t think that there is any way around the previous problem, though it seems clear that it would affect only a small fraction of the predictions. (The complexity theorists among the readers may remember similar ideas being used in a paper of Feigenbaum and Fortnow.)

Surely the task of scoring predictions must have been studied in countless papers, and the answers to the above questions must be well known, although I am not sure what are the right keywords to use to search for such work. In computer science, there are a lot of interesting results about using expert advice, but they are all concerned with how you score your own way of picking which expert to trust rather than the experts themselves. (This means that the predictions of the experts are not affected by the scoring system, unlike the setting discussed in this post.)

I would like to thank all those that contributed to the Turing Centennial series: all those who wrote posts, for sure; but also all those who spread the word about this, on blogs, twitter, facebook, and in real life; those who came to read them; and those who wrote lots of thoughtful comments. In a community where discussions over conference organizational issues or over the importance of matrix multiplication algorithms can become very acrimonious, I am impressed that we could have such a pleasant and troll-free conversation. This goes to show that in theory has not only the smartest and most handsome readers of the whole internet, as was well known, but also the nicest ones!

We will definitely do this again in 2054, to mark the centennial of Turing’s death.

A few days ago, I was very saddened to hear of the death of Sally Ride. A Stanford Alumna, Sally Ride became to first American woman to travel in space, she served on both the investigative committees after the two Shuttle disasters, and dedicated the past decade to the goal of getting young kids, and girls in particular, interested in science and technology. She cofounded, and directed, a non-profit foundation to further these goals, and wrote several books. After her death, it was revealed that she had been in a 25-year relationship with another woman, who was also the coauthor of her books and a partner in her foundation.

I think it is significant that a person that certainly had a lot of courage, determination, willingness to defy stereotypes, and to be an inspiration for people like her, felt that she could not be publicly out during her life. (In interviews about their books, Ride and her partner Tam O’Shaughnessy referred to each other as “friends”.)

Let’s hope that in 2054 it’s not just computer science professors in the West that are confortable being out, but also astronauts, movie stars, professional athletes, and so on.

[Leaving the best for last, here is Ashwin Nayak's post. Unlike the other posts in this series, Ashwin does not just talk about events, but he also gives us a view of his inner life at several critical times. What can I say to introduce such a beautiful essay? I got this: congratulations Ashwin! -- L.T.]

(Some names have been changed to protect privacy. Some events have been presented out of chronological order, to maintain continuity in the narrative. The unnamed friends in Waterloo are Kimia, Andrew, Anna-Marie, and Carl. I would like to thank them, Joe, Luca, and especially Harry for their feedback on a draft of this blog post. Harry offered meticulous comments, setting aside a myriad commitments. Most of all, I would like to thank my sisters and my parents for graciously agreeing to being included in this story.

For those not in theoretical computer science, FOCS is one of the flagship conferences on this subject. Luca is a professor of computer science at Stanford University, and Irit at Weizmann Institute of Science.

A prelude: I was born into a middle-class family from the South-West coast of India. I am the youngest of three siblings, and grew up in cities all over the country. My father served as an officer in the Indian army, and my mother taught in middle school until she switched to maintaining the household full-time. I went to IIT Kanpur for my undergraduate studies when I was 17. At 21, I moved half-way across the world to Berkeley, CA, for graduate studies. In 2002, after a few years of post-doctoral work in the US, I moved to Waterloo, ON, to take up a university faculty position.)

We were walking through art galleries in San Francisco when Luca brought up the Turing centenary events that were taking place around the world. None of the events celebrating his work referred to Turing’s homosexuality. Luca wondered whether the celebrations would be complete without revisiting this aspect of his life. As a response, he was thinking of having a series of guest blog posts by contemporary gay and lesbian computer scientists about their experiences as gay professionals. How would they compare with those in Turing’s times?

I wonder how much of my attention was on the art in the next few galleries. Would I write a post? What would I write? For me, sexuality is so deeply personal a matter that I’ve talked about it only with a handful of people. Why would I write about it publicly? Something Luca had said stuck in my mind: “The post could even be anonymous. That would be a statement in itself.” It took me back to my first relationship: I dated Mark for over three years and no one other than his friends knew. Times when I was on the verge of telling a friend about my relationships flashed by. I remembered the time I discussed with my immediate family why I would not get married (at least not the way they imagined). Times when students recognized me at events for gays and lesbians resurfaced, as did conversations with friends and colleagues grappling with openness. I would write a post, I told Luca.

That night, I got little sleep. Memories that I thought had slipped into oblivion loomed large. Read the rest of this entry »

[Rosario Gennaro is a cryptographer, and he has been at IBM for more than 15 years. (He must have started as a teen-ager.) On Monday, he will start his new job as a professor at the City College of New York and the Director of the Center for Algorithms and Interactive Scientific Software. In the middle of his move and of an internet-free vacation, Rosario found the time to write a guest post that goes in a quite different direction from the others. -- L.T.]

“David Hilbert … I suppose his name doesn’t mean much, if anything, to you? No, no? Well, there you are, you see? It’s the way of the world! People, never seem to hear about the really great mathematicians!”

The recent celebrations for Alan Turing’s centenary made me revisit the BBC movie of “Breaking the Code” that amazing Broadway play, with a wonderful Derek Jacobi playing Alan Turing. You can see the most astonishing bit of this play here:

a 6-minute tour de force monologue explaining in lay terms Godel's Theorem and Turing's discovery of undecidable problems.

But that's not what I decided to talk about. There is no question that Alan Turing's sexual orientation has played a huge role in the popularization of his figure and his work. "Breaking the Code" would not have been written if not for the unique personal story that accompanied Turing's exceptional contribution to Mathematics and Computer Science. Nor would NPR have run a story last month on the centenary. Neither Godel nor Hilbert (both mentioned in the above monologue) got such treatment.

While I wish that being gay were a sufficient condition for being a celebrated mathematician in the news (reserve space for my profile in the next issue of the New Yorker please), I wonder if being queer in some form is necessary. What can we do, as a community to make sure people know, not only Turing, but also Hilbert, and Godel, and Gauss. How can we make the Mathematics relevant, rather than the person. Can we get liberal arts majors, for example, to have a deep appreciations of the *ideas* and the *concepts* of Mathematics and Computer Science, even if they will never understand the proofs and the techniques? As I embark on an academic career after 16 years of research in a corporate lab, these questions have been occupying my mind. Others are wondering too …

Theoretical Computer Science, in my opinion, presents many opportunities on this front. Decidability, computational hardness, (pseudo)randomness … those are all concepts around which a philosophy class could be built. After all, as the fictional Turing says in the play, it's about telling right from wrong. I would love to develop such a class for liberal arts majors, and maybe the readers of "in theory" can help me by pointing me to similar classes that are already being taught somewhere. Yes, I am that lazy.

To finish off, being an opera queen (as any self-respecting homosexual should be) I have a not-so-secret wish to see "Breaking the Code" adapted into an opera. I think John Adams, whose work on physicist J. Robert Oppenheimer and the atomic bomb was mesmerizing, would be my top choice for a composer:

[Martin Farach-Colton is a professor at Rutgers, in the gayest computer science department in the country. He is well known for his work on algorithms and data structures. In the Fall of 1998, I was a post-doc at DIMACS and I lived in New York; since we had the same commute, I would sometimes get a ride from Martin. I was still quite new to the US, and I remember thinking it strange that Martin was the only person driving normally, while everybody else was going so slowly. Martin is the dean of out theoreticians, and he has written a very interesting post. I wish he hadn't given up so easily on the theme of sexism vs. homophobia. -- L.T.]

When Luca asked me to write a guest blog post on “Putting the Gay Back in the Turing Centennial”, I was happy to say yes. But I had a problem. If I were to write about being gay in the theory community, what could I write about? I’ve always been quite comfortable being openly gay in the theory community, and that doesn’t make for a very interesting story, does it?

But first, some context: I grew up in South Carolina, in an Argentine family. Both my family and my surroundings were deeply homophobic. When I moved away from home to go to medical school, I found myself in yet another very homophobic environment. Nonetheless, in 1986, I decided it was time to meet Mr. Right, and the first step was to come out to all my friends and family. Within 6 months I was living with Andrew. We’ll be celebrating 26 years together in a few months, as well as 9 years of marriage. Our twins are 12.

I wasn’t fully out at medical school, but when I started my PhD in Computer Science, I threw open the closet doors and was totally out from Day One. It would be years before I met another openly gay or lesbian computer scientist, and even more years before I knew of another LGBT theoretician. Yet I have found that being gay was no big deal within the theory community. Practically no one seems to care, and that’s the best kind of acceptance there is.

Remarkably, I felt this kind of open atmosphere at the very first FOCS I attended back in 1989. The world has changed a lot for gay people in the last 23 years, but the theory community changed earlier. Sure, people have said some homophobic things to me, but these were almost all minor incidents, and I’m also sure that those people would now be mortified by what they said 20 years ago. More often than not, when gay issues come up with my theory colleagues, they are mostly interested in topics like a technical analysis of how the fight for marriage equality is going. (I’ve been involved in this fight both here in the US — where there’s still plenty of work to be done — and in Argentina, which now has the most progressive LGBT laws in the world.)

What can explain the culture of the theory community? I turned to some of the women of my academic generation to see what it’s been like for them. After all, it seems that homophobia and sexism go hand in hand. Right off the bat, one of them torpedoed my premise. She pointed out that there have been plenty of gay men who are acknowledged as great geniuses. There is no stereotype to overcome with respect to being gay and being good at math. Indeed, in addition to Turing, Hardy was famously gay, as were Komogorov and his partner, the topologist Pavel Alexandrov. I’m not placing myself in such exalted company but merely pointing out that perhaps I had it easier than women in the field because I had fewer stereotypes to overcome.

I found general consensus that, although the theory community is not free of prejudice and stereotype, it’s a comfortable place for a lot of people. Perhaps it’s not just theory. My own department had, at its high-water mark, four openly gay faculty, two of whom were recruited as a couple. I also found Google very gay-friendly when I worked there in the early ’00s.

So, really, I feel like I have nothing substantive to say on the subject. And maybe the best news. To paraphrase Tolstoy, happiness is dull.

Two more posts are coming soon. Meanwhile, here is a wonderful interview with Robert MacPherson, which is part of an interview series by the Simons Foundation. Although the interview does not mention Turing, it does mention Kolmogorov.

(via Not Even Wrong)

It is late Spring in 2000, and I am to have lunch in New York with Ran Canetti and Ronitt Rubinfeld. Ronitt is already there, and Ran arrives a bit late and asks what we are talking about. “I told Ronitt that I am gay” I say. “Oh…” says Ran “Congratulations!

[Sampath Kannan is best known for his work on program checking (which was introduced in a joint paper of Sampath and Manuel Blum), computational biology and streaming algorithms, and also for his outstanding service to the computer science theory community, first at NSF and now at the Simons Foundation. He has contributed a personal and deeply felt post to this series.]

I discovered Turing the mathematician long before Turing the gay man. Growing up in India in the pre-internet era, Turing’s story, had I known it, would have probably sparked an earlier awakening. It didn’t help that neither our field, nor the philosophical milieu of my upbringing encouraged me to pay attention to sensory perceptions and emotional reactions to them – I couldn’t, imagine being a physicist, although others who grew up in the same circumstances have gone on to do exactly that. However, I have had a growing realization that acknowledging one’s own perceptions and reactions is important for one’s happiness and well-being. Given all the obstacles that people face to discovering who they truly are, it is important that there are more positive role models for them to look to.

Of course things have changed a lot over the last three decades. Our field, most universities in the west, and IT workplaces are friendly places for LGBT people. The way we view Turing’s personal life is evidence of this change. My own university was one of the earliest to set up an LGBT center, way back in 1982. It was also one of the first to offer domestic partner benefits and most recently, in a symbolically important gesture, it decided to “gross up”, i.e., to pay LGBT people more to offset the tax disadvantages they suffer on benefits to their partners. While Penn is on the leading edge of some of these changes, it seems clear that this is a trend that will sweep universities and research labs. Thus fear of the reaction at the workplace need no longer be a reason for people coming out of the closet.

There still remain the other obstacles – personal and social – and these are not so easy to overcome, especially for the many non-westerners in our field. How much of an embrace does one need from one’s friends and family? Or is acceptance in some form good enough? How does one withstand the pressure to marry? The homophobia of peers in school and college? In my time the elite technology institutes in India were male-dominated and unthinkingly homophobic. But here too things may be improving – a gay and lesbian group is thriving at IIT Bombay and it is celebrating its first birthday with more than 100 members, a majority of them on campus! Perhaps concomitantly, the number of female students on these campuses is increasing as well.

If only Turing were alive today …

[Günter M. Ziegler is a Geometer and Discrete Mathematician with interests in Topology, and a professor at the Freie Universität Berlin. Readers of in theory might know him as one of the authors of Proofs from THE BOOK. Tomorrow, Der Tagesspiegel, Berlin's leading newspaper, will publish a piece by Günter on Alan Turing. Since readers of in theory are awesome, they get to see it a day before, and in English. Please join me in thanking Günter for his lovely and personal contribution. -- L.T.]

Dear Alan,

calling you “Alan” is OK and appropriate, I hope? Mathematicians of your time used to be much more formal among each other, I know, but that has changed with time. And gays tend to be still less formal, so of course we’d be on first names basis nowadays. A kiss is a common form of greeting. Still, you are 6 years younger than both my grandfathers, 16 years older than my father. And you killed yourself before I had a chance to meet you, 11 years before I was born. You are so close, so far!

I know you (at least it feels like it!) from the biography “Alan Turing. The Enigma” by Andrew Hodges – I happened to come across it in the summer of 1987, right after finishing both my PhD and starting my coming-out at MIT. The cover of my paperback copy has an attention-grabbing blurb

The extraordinary story of the brilliant scientist who broke “Enigma,” Germany’s most secret World War II code, who pioneered the modern computer age, and who finally fell victim to the cold-war world of military secrets and sexual scandal.

My copy shows all signs of having been read intensively, its cover is worn, its binding starts to come apart, and some passages are underlined or marked. Thus, for example, I marked

“He had wanted the commenest in nature; he liked ordinary things. But he found himself to be an ordinary English homosexual atheist mathematician. It would not be easy“

on page 115.

“It would not be easy”? For me – an ordinary German homosexual atheist mathematician – it seemed easy: I was ambitious, a bit over-motivated, I got a lot of support, and I got a lot of freedom for my development. Yes, I had to work hard, but that was since Mathematics is a difficult subject, and also since of course I did not have your talent, but the difficulty of my subject was what had attracted me in the first place. But I never ran into any real problems because I was gay. I am grateful for the freedom and the support I got – and today, out of gratitude, I try to pass some of that on, to my students, to the greater University community, and to our graduate program, the “Berlin Mathematical School”, where I am the chair of the committee for “Mentoring, Gender and Diversity”.

You, in contrast, in 1952, became a victim of British laws and courts, as an openly gay man. They confronted you with the inhumane alternative “prison or chemical castration”. You chose the latter, an estrogen hormone therapy. You, the runner, who competed in qualification races for the marathon at the 1948 Olympic Games in London – now you were growing breasts. Depression. Suicide in 1954, a few days before your 42nd birthday.

This is how England treats her geniuses, her heroes? Only in 2009 Prime Minister Gordon Brown declared, under pressure from thousands of signatories of an internet petition, the apologies of the British government. A slightly pathetic “I am sorry, we are sorry”:

Thousands of people have come together to demand justice for Alan Turing and recognition of the appalling way he was treated. While Turing was dealt with under the law of the time and we can’t put the clock back, his treatment was of course utterly unfair and I am pleased to have the chance to say how deeply sorry I and we all are for what happened to him.

So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better.

Is this enough? Would you think that this is enough? Would you accept the apologies? Initiatives that ask for an official posthumous pardon, for the acknowledgment that the conviction as such was unjust, have not been successful up to now. A new internet petition to the British Government is on its way, up to now it drew nearly 35.000 signatures. A pardon? The verdict has to be: Not guilty! There was no crime!

Tomorrow, on Saturday, we celebrate your hundredth birthday. It is marked by activities around the globe. In Cambridge, England, where as an undergraduate student you wrote “On computable numbers”, they are having a “Turing Centenary Conference” this week. But this is a greeting and an invitation from Berlin, where we organized a huge party for you: The Berlin 2012 Gay Pride Parade, which we call “Christopher Street Day”, got a science motto “Wissen schafft Akzeptanz” in your honor. It’s your party, Alan! And indeed, also taking part in the parade, on float number 11, is the British Embassy!

Not only as an individual, and as a gay man, but also as a Professor of Mathematics at Freie Universität Berlin, the Berlin “Free University”, whose academic and personal liberties you never had the opportunity to enjoy, I take special pleasure in announcing the party, and to be part of it.

The 2012 Berlin Gay Pride Parade may be the largest birthday party for a Mathematician ever: we expect half a million participants. Alan, you deserve it.

Happy Birthday, Alan!

2012 The Alan Turing Year: www.turingcentenary.eu

Alan Turing Petition: submissions.epetitions.direct.gov.uk/petitions/23526

Turing Centenary Conference, Cambridge, 18.-23. Juni 2012: www.cie2012.eu

Gay Pride Berlin: www.csd-berlin.de

Günter Ziegler