Computational Complexity

Result of the Year goes to the new bounds on Matrix Multiplication by Andrew Stothers and Virginia Vassilevska Williams. It's not every...

Two announcements on Monday connected to my two Alma Maters mark the changing face of universities. New York City chooses Cornell and the...

How are Mitt Romney and Scott Aaronson similar? Different? Similarities: Both live in Massachusetts. Actually, Scott lives there but i...

In my post last week, my commentors took me to task on my prediction that cars will drive us in ten years. Some thought Americans would wis...

In my last blog I asked you to look at this problem, try to solve it, and tell me if you think it is too hard for a HS competition. (I meant...

The Univ of MD HS Math Competition has two parts. Part I is 25 multiple choice questions in 2 hours (4 points for a correct answer, -2 for a...

Ask your friends if they'll be driving an electric car in ten years. The answer: No, cars will be driving us . Today is the 105th anni...

The recent discussion on Matrix Mult inspires the general question of WHAT IS A BREAKTHROUGH? Last year I tried to get an intelligent discus...

On Saturday, Terrence Fine gave a talk on probability at a workshop at Northwestern. Before the talk he asked who thought probability was s...

(Guest post by Ryan O'Donnell) Lance and Bill have graciously let me plug my recently begun book/blog project, analysis of boolean ...

(INNOVATIONS CONFERENCE: here ) (While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here . Ou...

In the 2011 Complexity proceedings there are three papers that analyze complexity classes, Ryan Williams' great paper on ACC, Russell I...

I just finished the Walter Isaacson biography of Steve Jobs. Seems like everyone in the blogosphere has analyzed every sentence in the book...

Because some things are too long to tweet and too short for their own blog post. What's the algorithm for the perfect sushi? Enjoy it ...

Consider the following email I got: Dear Professor, 1. Antarctica Journal of Mathematics 2. ArchimedesJournal of Mathematics 3. Bessel...

Take the state of Pennsylvania and draw the two diagonals. Where they cross is the small town of State College, home of the Pennsylvania Sta...

A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answ...

Digital cash systems have come and gone but Bitcoin seems to be doing okay. By request I am giving a lecture about Bitcoin in my crypto cla...

For these looking for an academic job in computer science next year, best to start on the jobs pages of the  CRA and the ACM . Both lists s...

What is the purpose of an academic journal? To provide a permanent vetted record of a specific research endeavor. The ways we communicat...