Computational Complexity

Last week I started an experiment using instant messaging. I thank the many of you who sent me IMs, a great way for me to meet you, the ...

Let f be a function that maps Σ n to Σ n . Let U represent the uniform distribution on Σ n and D be the distribution that one gets by ap...

A quantum computing graduate student sent me email over the weekend. He had thought he had proven some surprising results about the class ...

Here is one of my favorite examples of a bad proof for what turns out to be a correct theorem. Theorem: If NP is in BPP then the whole pol...

How has the internet most affected the study of science? In one word: communication: the ability for scientists to discuss and share their ...

There is a big reorganization in the CISE directorate of NSF. To understand what's happening, let's review the previous structure.....

There are two computer science departments on the University of Chicago campus. The one I belong to, a department in the physical sciences...

This is for my friends in Boston who suggested I do a sports post. One of the great parts of my job is working with people from around t...

Just prior to the FOCS conference, Avrim Blum gave a tutorial on machine learning and Dana Randall gave a tutorial on mixing. As the talks...

Today is Columbus Day, a minor holiday in the states. There is a great saying about Columbus: He is not famous for being the first person to...

With FOCS starting this weekend, here is some advice for students attending a conference. What is the purpose of a conference? Disseminatin...

Next week is the 44th FOCS Conference in Boston. FOCS, the Symposium on the Foundations of Computer Science is, with STOC, one of the two...

While on the topic of awards, we have a new "genius" in the theoretical computer science community. Computational geometer Erik De...

The Nobel science prizes will be awarded next week: Medicine on Monday, Physics on Tuesday and Chemistry and Economics on Wednesday. Nothi...

I have tried to keep politics out of this weblog with the exception of issues related to science, in particular science funding and immigr...

What is a one-way function , intuitively a function that is easy to compute and hard to invert? Taking this intuitive idea to a formal def...

UCLA Professor Andrew Kahng gave this wonderful speech to the incoming computer science graduate students. While designed for UCLA, with mi...

We just got email that Proof , a movie adapted from the play , will be filmed in and around the University of Chicago campus over the next f...

Christos Papadimitriou has been exercising his creative talents. He has a new book Turing (A Novel about Computation) building a love story...

There has been some buzz about the paper Resource Bounded Unprovability of Computational Lower Bounds by Tatsuaki Okamoto and Ryo Kashima...