Scott Aaronson wins Trevisan Award? Prize? Medal? Statue?

 1) Congratulations to Scott Aaronson for winning the first Trevisan Award.

The Trevisan Award is in memory of Luca Trevisan and recognizes expository work in Theoretical Computer Science. It is given out by the ACM. The ACM announcement of Scott's award is here. Scott blogged about winning it here.

2) When preparing this blog post, I googled Trevisan Award. The first hit I got was this. That site says the award was for significant research. Hmmm. My first thought was Scott has, in fact, done significant research. Perhaps I misunderstood the award. I shared these thoughts with Lance who pointed out I was at the wrong website:

Scott won the Trevisan AWARD.

There is also a Trevisan PRIZE. This was the first hit I got when I googled Trevisan Award. 

There is not yet a Trevisan MEDAL. Give it time.

 
4) I then realized I did not actually know the difference between an award, a prize, and a medal.

a) What are all the ways to honor someone in academia?

b) How do they differ?

5) I asked our future AI overlords:

In academia there are PRIZES, AWARDS, MEDALS. Other ways to honor people in other fields are Ribbons and Trophies. Are there other ways to honor people? How do they differ?

Chatty gave me 10 pages of interesting material that appeared correct, which is about the best one can hope for. See here. In case you are thinking tl;dr, here is a short version focused on academia, with some of my own thought mixed in.  

a) Awards: General Recognition of excellence. May or may not involve competition (that's a tautology). I aspire to win the Montgomery Burns Award for Outstanding Achievement in the Field of Excellence.

b) Prizes: Usually competitive. Often recognizes a specific breakthrough.

c) Medals: Prestige and ceremony. Often accompanied by an actual medal.

d) Fellowships: Recognizes a substantial body of work.

e) Named lectures: Prestige plus airfare.

f) Named professorships: Prestige plus discretionary funds.

g) Election to academies: Peer validation with nice stationary.

h) Honorary degrees. A way to get a celebrity speaker at a graduation.

i) Statues. The only academic one I know of is The Slide Rule Statue, see here. 

Academia has many ways to honor people. Apparently the hard part is keeping track of which noun goes with which person.

The real award was the friends we cited along the way.

 

Prediction Markets Redux

For those very long-time readers this blog extensively covered prediction markets from 2006 to 2008. In a prediction market, you have a future event, such as the winner of an election, and a market that pays off one dollar if that event happens and nothing if it doesn't. The price of this market corresponds to a predicted probability that the event will happen. 

I worked with David Pennock and Yiling Chen to create an interactive map that colored every state based on how likely it was to go Democratic or Republican for both the presidential, gubernatorial and Senate races.

This all ended when Intrade, the source of the data that we used, went out of business after its CEO died climbing Mount Everest and may have embezzled money from the company.

In 2016 prediction markets went out of favor after badly predicting against Brexit once and Trump twice. 

But what's old becomes new again. Prediction markets are back with a bang, with Kalshi and Polymarket providing real money markets open to U.S. citizens, something we didn't legally have, except for very low stakes, twenty years ago.

Prediction markets play two distinct roles:

1. As a betting system so people can put their "money where their mouth is" based on their beliefs.
2. As an information aggregation system, to use the wisdom of the crowds to predict future events.

Sometimes these roles conflict with each other. With real money comes real greed and we've seen some recent issues of insider trading, most notably a US soldier who used classified knowledge about the then upcoming raid in Venezuela to net $400K on Polymarket. 

Insider trading will likely lead to better predictions, but those who have bet on that market might feel cheated. In the short run, insider trading might be a good thing, but in the long run, if we scare away participants because they're afraid others who have more information will take advantage of them, then we have fewer people in the market making it harder to draw upon the wisdom of the crowds. 

Another challenge for prediction markets is determining how the market pays off. You need to come up with a very specific definition of what it means for the market to pay off, but strange circumstances can lead to unexpected results. Back in 2006 North Korea launched a test missile outside the country but the market for that event paid off zero because the U.S. Department of Defense never verified that the missile actually left North Korean airspace. 

The market I like to see is factoring the RSA numbers by a given date. Very easy to verify. Some people might buy such a security, expecting quantum computing to be factoring numbers soon. And then I can make some money by betting against it. 

Searches Are Weird! No they're not! Bad coding style?

In David Marcus's guest post on good coding style (see here)  he reviewed a book from 1986 called  "Professional Pascal."

I wondered if it was still in print and could be bought:

1) I went to Amazon and searched all products for Professional Pascal. I got this, which is not that book.

2) I then restricted to books, and I got the same, though later on the page I got a relevant book, here.

3) I then searched for Professional Pascal on Google, and got the Amazon site for the book here.

David thought this was weird. I did not. As I put it:

A computer does something which makes no sense. This is common, hence it's not weird.

Why did the search from outside of Amazon do better than the search inside of Amazon?

Speculation

1) Search is just a really hard problem.

2) The coders at Amazon did not use good coding style. They should read the book. If they can find it. 

When do we know someone has died

As the blog of record in computational complexity, we like to bring attention to those in the community who have left us. When we learn of someone in our field who has died, Bill and I will talk to each other and decide whether we should do a social media post or a full blog post, and who should write it, Bill, me, or someone else. In fact, if I call Bill, he'll often answer the phone with "who died?"

We also remember those who passed away during the year in our end-of-year post.

One challenge is how we actually know when somebody has died. Consider Michael Rabin. His death was announced on Wikipedia based on the following announcement in Haaretz, an Israeli newspaper.

Haaretz Obit (Translated by Google)

That's a pretty simple obituary for a very famous computer scientist. Rabin is a common name in Israel, and there easily could have been another professor named Michael Rabin somewhere in the country. Every mention of Michael Rabin's death that I saw was just citing the Wikipedia article, nothing from Tal Rabin or some other source that cited the family.

By the time Bill put up the first Rabin post on April 22, we figured that had our Michael Rabin not died, someone would have come forward about it. 

Tony Hoare is a different story, where our blog was one of the first to break the news. I heard from two separate people that they had heard from the family that he had passed away. It helped that I was in Oxford at the time, where Hoare spent much of his career.

And too often a theoretical computer scientist passes away but the news never reaches us and we don't remember them. It's always sad when someone passes, but it is a good opportunity to remember how they helped shape our field. But we need your help to know when someone has passed away. So if you know someone in our community has passed away, please let us know, and how you know, so that we can know we know.

A few notes on Michael Rabin

Michael Rabin passed away on April 14,2026. I blogged about him here. 

My post listed results of his that proved upper and lower bounds on problems. My point was that he proved upper and lower bounds for MANY different levels- from decidable to regular. And I am sure I left out some of his results. 

Here are some things I did not mention.

1) Rabin and Scott shared the Turing Award in 1976.  My not mentioning it raises the following question:

If I want to say someone has an impressive set of results which is a better way:

listing the awards they've won, or

listing  their results. 

I leave this to the reader. 

2) I had Rabin for two graduate courses at Harvard: Algorithms and Complexity Theory. He was a great teacher and gave insights into the results, some of which he had either proven or worked on.

3) I recalled thanking him in my PhD Thesis. So I dusted it off to see what I had said: 

The many courses I have taken at Harvard and MIT have helped me create this thesis. I am especially indebted to Michael Rabin, Mike Sipser, and Michael Stob for their excellent courses in algorithms, complexity theory, and recursion theory. Their pedagogy has been an inspiring example of what good teaching can and should be.

What is the probability that all three great teachers were named Michael? I do not know, however, I suspect Michael Rabin could have told me.