Japan has produced some excellent theorists, like Seinosuke Toda who won the 1998 Gdel prize for his paper reducing the polynomial-time hierarchy to counting...
Here is an interesting problem given by Muthukrishnan during his talk in the New Horizons workshop. Start with an array A of n+1 entries each consisting of an...
I finally read Clayton's Christensen's The Innovator's Dilemma . A few years ago an NEC executive gave a talk using the ideas in the book to explain NEC's...
February Edition How do we formalize the notion of efficient computation? Two important papers from the 60's suggest polynomial time algorithms are efficient ...
Scott Aaronson has a fun paper in the complexity column of the new SIGACT News where he addresses the question: Can NP-complete problems be solved efficiently...
The Tomagotchi craze has hit my daughters' school. The Tomagotchi is a small toy with a few buttons and a screen where you can play with a cartoonish creature....
This week I visit CWI in Amsterdam where I spent my sabbatical year eight years ago and continue working relationships with many people here especially Harry...
When I visit Amsterdam I rent a bike for much the same reason I rent a car when I travel to New Jersey. CWI is in the east part of the city and does not have...
In 2005 I have already traveled on five trips to four different countries on three different continents. My travel comes in bunches. I didn't teach in the...
My father passed away 25 years ago today. I thought I would share some of the lessons I learned from him. Once you win an argument, stop arguing. Always play...
Given a k-tape Turing machine can we reduce the number of tapes without too large an increase in time and space (memory)? Not just an esoteric question, tape...
From Chris Bourke : I've created a LaTeX package for typesetting complexity commands ($\P$, $\NP$, etc). Its available on CTAN . Not only does it define ...
A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied "I can recognize great...
I have a brother who worked in the music industry and got us first row tickets to Kool and the Gang. I have a brother who was an entertainment lawyer who...
Using performance-enhancing drugs has become a major issue in national and international sports, most recently in Major League Baseball in America where many...
Mike O'Donnell tells a story of talk he saw once where the speaker considered the following recursive program: f(n) := output 0 if n = 0; output f(n-1)...
A reader asks I wanted to ask you something about the Savitch and Immerman-Szelepcsnyi theorems that I saw you have in your weblog. In both thorems we have...
Speaking of space complexity, Adam Kalai, Adam Klivans and Rocco Servedio have extended Reingold's result to show that every language in randomized logarithmic...
When computational complexity gets accused to having no connection to reality, I bring up the story of the PRAM (Parallel Random Access Machines), a complexity...
From a poster in my building: What is the longest song? " 0 bottles of beer on the wall." Happy Mathematics Awareness Month ! April is also National Poetry ...
A perfect spring day in Chicago and all of my afternoon meetings mysteriously canceled so I took visiting Portuguese professor and avid soccer fan Luis Antunes...
A recent conversation with a graduate student. Student: I couldn't find the paper online. Me: So walk over to the library and get the paper there. Student: But...
Little things that annoy me in research papers. Declarative first sentences of the introduction, like "Analyzing Left-Handed 12-SAT is a key approach to...
A guest post by Michael Mitzenmacher Lance nicely invited me to expand on my views on the format for conference submissions. Currently, I am on a PC using the...
A simple trick that every complexity theorist should know but, based on some recent conversations, not every complexity theorist does know. Roughly speaking...
New Balance has been heavily advertising some questions about sports so I'd thought I would give my own discussion questions about academics. You've been...
There is some buzz about a new construction of probabilistically checkable proofs by Irit Dinur. The PCP theorem, first proved by Arora, Lund, Motwani, Sudan...
Haipeng Guo wins the math poetry contest with the poem below. Congratulations and thanks to all that participated. When a P-man loves an NP-woman Been a happy...
You have probably heard this story by now. Some MIT students created a computer-generated paper accepted to a non-reviewed session of the Systemics,...
March Edition This month we honor the papers that gave us the first NP-complete problems and marked the official beginning of the P versus NP question. The P...
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.
