Computational Complexity

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...

Berkeley complexity theorist Luca Trevisan travels to China and you can read all about it in his new weblog In Theory . But suppose you co...

A graduate student recently said Computational Complexity is not a Spectator Sport meaning that to truly understand and appreciate computa...

Bill Gasarch sends in some links on recent activities at Harvard. The Harvard alumni magazine has an "objective" (according to Gas...

At Dagstuhl last week Jehoshua Bruck gave a talk giving some interesting open combinatorial problems that have real-world applications. For...

February Edition After the work of Cook and Karp popularized the P versus NP question, computer scientists immediately tried hard to prove...

Because the state recently banned nearly all abortions, there is a call to boycott South Dakota , coincidentally where my family vacationed ...

Alex Lopez-Ortiz points out that this month's SIGMOD Record has an interview with Moshe Vardi from Rice University that touches on sev...

Live from Schloss Dagstuhl, the fifth Complexitycast . Our guest is Eldar Fischer who talks about his love and joy, Property Testing. For mo...

Last week's Numb3rs episode "Mind Games" centered on a purported psychic causing the mathematician Charlie Eppes to exclaim ...

This week I am at the Dagstuhl seminar Complexity of Boolean Functions . Schloss Dagstuhl is an isolated conference center in Southwestern ...

It happens every spring, America's favorite binary tree, the NCAA Men's Basketball Tournament Bracket was announced Sunday night. ...

I receive several requests to comment on various papers claiming to prove P = NP, P ≠NP, or the independence of the P versus NP question on ...

University presidents come and go but Lawrence Summers announcement last month that he will resign as Harvard's president has and still ...

Michael Nielsen returns to blogging after seven months since his last real post. He talks about his new Science paper Quantum Computation ...

In this month's CACM, CMU Chair Jeannette Wing wrote a neat Viewpoint column Computational Thinking (with related slides ). In the arti...

Thomas C. Hales talked at the recent AAAS meeting about his proof of the Kepler conjecture. From a New Scientist item In 1998 Hales submit...

My post A Referee's Boycott generated quite a discussion in the comments, particularly about Elsevier. Paul Beame asked about why the E...

The ACM announced the 2005 Award Recipients . Looks like it is for real this time, here is the press release on Peter Naur's Turing Aw...