This Saturday comes the annual William Lowell Putnam Mathematical Competition . The contest is open to undergraduates at American universities. Any number can...
Luca asked about the topics in the complexity courses I took in 1985 and 1986. I dug up my old course notes and wrote down what was covered. Some more in the...
Many of you submitted papers to the Complexity conference by yesterday's deadline, now you should let the world see them. Submit your papers to an archive...
Someone asked me recently how I became a complexity theorist? After all most high school students don't say they want to be a theoretical computer scientist...
Guest Post by Bill Gasarch with help from Harry Lewis and Richard Ladner. What are the surprising results in theory? By surprising we DO NOT mean surprising...
This week I am visiting the University of Texas in Austin. Yes, another football school , but they also have a boffo complexity group with Anna Gl, Adam...
We have seen many exciting papers based on the unique games conjecture for example that improving the Goemans-Williamson approximation algorithm for Max-Cut...
Nicholas Kristof writes in a New York Times op-ed column The Hubris of the Humanities (paid subscription required) that the lack of appreciation for science...
In my second Complexitycast , Scott Aaronson and I try to answer the question "What should physicists know about computational complexity?" MP3 (21:52, 3.8MB)...
Christos Papadimitriou gave an overview talk at the NIPS conference last week and mentioned the new result by Chen and Deng showing that, given the payoff...
In the chair's letter of the December SIGACT News , Richard Ladner points to this and other weblogs for discussions about the FOCS Business meeting panel...
After I choose my ten favorite theorems in the decades 1985-1994 and 1995-2004 , I went back to the first decade in complexity. Here is a recap of my ten...
A recent comment made the mistaken assumption that if NP is in BQP (efficient quantum algorithms) then the whole polynomial-time hierarchy lies in BQP. We do...
I've been catching up on my Tivo on the second season of Numb3rs, the CBS television series about a math professor Charlie Epps who uses math to help his...
For the first time in my lifetime, Christmas and Chanukah land on the same day. So to all my readers, Happy Holidays! And what do we find under our theory...
A new US game show started last week, Deal or No Deal hosted by Howie Mandel (the same Howie from this post ). A New York Times article describes the game as a...
Many fields, like mathematics and economics, have a civilized recruiting process. They have their annual conferences in January with organized meetings between...
Paper of the year goes to Irit Dinur's PCP Theorem by Gap Amplification . We will never teach the PCP theorem the same way again. Concept of the year goes to...
Edited from an email by Jan van Leeuwen and Jiri Wiedermann The year 2006 will be a special year for the foundations of logic and theoretical computer science...
The Internet has led to a complete shifts in how we deal with storing and sharing information, but when it comes to academic papers the changes we see are ad...
We need to rewrite the traffic laws in this country because they don't handle flying cars. We don't have flying cars, you say. We might have flying cars in the...
Finding the 5th moon of Jupiter was a big deal. Finding the 14th moon was a big deal. But it's hard to get excited about the 63rd moon. Now imagine if Jupiter...
This week I am making my nearly yearly visit to CWI in Amsterdam, where I spent a sabbatical year in the 90's. I will sit on the opposition on Troy Lee's Ph.D....
My first trip to Amsterdam came during a whirlwind European tour in the summer of 1984 during my undergrad years. My second trip was for the 1994 Complexity...
Every year I seem to write more letters, letters for those applying to graduate schools, letters for those looking for their first postdoc or assistant...
In the third Complexitycast we talk about the Dutch Defense with new Ph.D. Troy Lee and several of the participants in his ceremony. MP3 (18 minutes, 3 MB) --...
We watched the Chicago Bears Football team lose to Carolina with some friends who were extremely pessimistic the entire game, even though the game remained...
I have written up my ten favorite theorems for the decades 1985-1994 , 1995-2004 and 1965-1974 . This year we tackle the remaining decade 1975-1984, the second...
From Sanjeev Arora Bill Steiger of Rutgers is the new NSF program officer in charge of Theoretical Computer Science (TCS) and he has assumed this position now....
I am on vacation next week and I've lined up Bill Gasarch as a guest Blogger in my absence. But today we have a guest post from Kamal Jain. This is a long post...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
