Computational Complexity

If you have an academic job offer, what next? Don't forget to negotiate. I wrote a post on negotiating last fall and in particular you ...

Kurt Gödel came into our world one hundred years ago today. Gödel's incompleteness theorems changed the way we think about mathematics...

Tomorrow marks the hundredth anniversary of the birth of combinatorialist Richard Rado . Rado is the second most famous mathematician born...

"…which also gives better heuristics for the Traveling Salesman Problem." "Don't you mean the Traveling Sales person Pr...

An anonymous graduate student asks Why do theory students have to take systems courses? Most American Ph.D. programs have distributions re...

Luca and his commentors get dreamy-eyed over Berkeley but not everyone has such fond memories of that place. I arrived in Berkeley for gra...

A few days ago I put a look of horror into one of our graduate students when I went up to him and simply said "You should be careful ab...

March Edition In 1976, Juris Hartmanis and Leonard Berman defined the isomorphism conjecture: For all pairs of NP-complete sets there is...

Venkat Guruswami talked at TTI last week giving an overview of recent work in list decoding. Someone asked him about practical applications ...

The iCal standard allows sharing of events and calendars. The standard has been around for many years and has been popular with Apple user...

Microsoft just announced their Academic Search , a direct competitor to Google Scholar . Scholar is incredibly useful at tracking down elect...

The EATCS has announced the winners of the Gödel Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena for their paper Primes in P . I st...

A good reader question. I was curious if you had any discussions on what kind of math background new graduate students need to have? For in...

When you are asked to referee a paper you need to follow a set of ethical guidelines that are rarely spelled out and often ignored. Here are...

From Jay Leno's monologue on Monday's Tonight Show Scientists have been working on a device that will tell when you are boring or i...

From an assistant professor comes a question How many Ph.D. students should a professor advise? There is no single answer. The usual cons...

Ten years ago today federal agents went to a remote cabin outside Lincoln, Montana to arrest one Theodore Kaczynski, also known as the Unabo...

The Chicago White Sox have raised their championship banner and started a new season with a rain-delayed win . A team wins the World Serie...

In 1986 during the prehistory of Hardness vs. Randomness, Sipser showed that if time does not have nontrivial space simulations one can der...

An anonymous commenter asked Many of us seniors are currently choosing among PhD programs. As you probably know, we are expected to come to...