Computational Complexity

We had another solid year for theoretical computer science and computational complexity with many exciting results such as the polynomial ...

Today is the 100th anniversary of the birth of John von Neumann , one of the greatest mathematicians of the 20th century. Let me discuss t...

Nothing like this Chicago Tribune story to ruin your holidays. Apparently the Illinois Board of Higher Education has launched a study of fa...

On Saturday I visited the Einstein Exhibit at Chicago's Field Museum . Some manuscripts and letters and a nice exhibit explaining why ...

Time for another of my favorite open problems. Does NP=UP imply the polynomial-time hierarchy collapses? UP is the class of languages...

Yesterday the New York Times Magazine had its annual "The Year in Ideas" issue. Ideas Futures Markets in Everything and Prov...

Every scientific field has their own rules for the order of authors in a paper. In theoretical computer science, tradition dictates that we...

Want an easy rule to greatly improve your writing? Just avoid the following words, particularly in the abstract and introduction of your pa...

Over the last 15 years, two very active research areas seem at odds. Derandomization results have shown us that we can often remove random...

Paz Carmi, Yinnon Haviv and Enav Weinreb from Ben-Gurion University have solved the regular language problem I posted last month. The ...

The Cornell University Library has announced it will drop a substantial number of their Elsevier subscriptions, part of a general proble...

First an update on NSF program solicitations: The Formal and Mathematical Foundations cluster has posted its solicitation which includes ...

I hope you all got your Complexity submissions in on time last week. Now let the rest of the world see your work. Make them into technical...

In the left column of this weblog's homepage, I've added a new "weblogs" section to list the academic weblogs that I have...

XML (eXtensible Markup Language) has become quite a popular data format in recent years. XML roughly corresponds to a tree. For example, ...

I thought I should mention some of my favorite and most frustrating open questions over the years. Here's one of them: Let f:{0,1} n →{...

Over the years a number of localized theory workshops have developed which bring together researchers from around the area to mingle and l...

Back in my science-fiction reading days, I particularly remember one editorial written in one of those anthology magazines about 1980: In ...

Here's a problem from Janos Simon. For a set A, let L(A)={x | for some m≥0, x m is in A} Simon asked, as a homework problem, to s...

[I will do this just once. Feel free to use the comments link to mention your own institution.] We are seeking theory graduate students ...