Each day a weatherman gives a probability p of rain for the next day and each day it either rains or it doesn't. How do we judge the quality of these...
Each day a weatherman gives a probability p of rain for the next day and each day it either rains or it doesn't. How do we judge the quality of these...
One of my students wanted me to complain in my weblog at the lack of wireless access in conferences like the recent SODA meeting. Sorry but I don't agree. I've...
The DIMACS Workshop on Information Markets drew a neat crowd, a mix of computer scientists, economists (mostly experimental) and members of industry from...
My old apartment-mate Eric Schwabe came over to watch the game last night and brought along old posters he had from the Super Bowl parties we used to throw as...
Suresh has been doing a fine job reviewing the Numb3rs episodes. Nevertheless Bill Gasarch wanted to write a guest post on the P versus NP episode which was...
Thomas Garrity's book All the Mathematics You Missed [But Need to Know for Graduate School] has a section on P versus NP which says The N in NP is somewhat of...
Introduction We should start off off my list of favorite theorems from the first decade of complexity with the seminal paper in complexity, the one that gives ...
I have one word of advice that applies especially to junior faculty: No. You will be asked to referee papers, look at graduate applications, look a faculty...
A reader question (anonomized): How should you decide whether to go into industry? Are there ways back after you have sold your soul? The occasion: I got an...
I've seen several pointers to this nice article on origami and Erik Demaine in the Science Times section of today's New York Times but also check out the...
For this weblog it's the Super Bowl, the Grammys and the Oscars all rolled into one: Announcing the accepted papers of the 2005 Conference on Computational ...
I've already heard from several graduating students who have had few or no interviews scheduled and are really worried about finding a job next year. Don't...
Scott Aaronson weighs in on last night's NUMB3RS episode "Prime Suspect". Minor Spoiler Warning. Last night's NUMB3RS again centered around complexity. A...
We know only a few natural problems in NP that are not known to be NP-complete or in P. The two most often named are factoring and graph isomorphism. Another...
Below the paid ads, Gmail gives me related links on the side of my email. In a discussion on a bad P NP proof (don't ask) Gmail pointed to this interesting...
I'm off to Japan for a Workshop on New Horizons in Computing that kicks off a new theory project sponsored by the Japanese Ministry of Education. This will be...
Two fellow (and slightly better known) Chicago professors Gary Becker and Richard Posner run a joint weblog on various social issues. This week they tackle the...
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 ...
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.
