Computational Complexity

Nicole Immorlica reports on the NSF CISE Broader Impacts Summit held last week in DC. We've all seen it. Most of us have even written...

Some random thoughts about quiz shows. THOUGHT ONE: There could be a quiz show based on P and NP. We all think that FINDING an answer is...

There was a Women in Theory Workshop at Princeton From June 19-23. ***SORELLE***, who was there, has some intelligent and interesting t...

How to best describe what we do to the layperson? It depends on what you mean by layperson . I was in Austin Texas visiting my nephew Ja...

I set up a new blog, Future of STOC to discuss role of our main conference and how to achieve it. At STOC this year we had a relatively l...

(Guest Post by Vijay Vazirani) Foundational ... or Simply a Curiosity? Conventional wisdom has it that whereas linear programs have...

( Reminder:Deadline for submitting to special issue of Theory of Computing in honor of Rajeev Motwani is July 30. See here. ) CCC ...

László Lovász wins the Kyoto Prize for "Outstanding Contributions to Mathematical Sciences Based on Discrete Optimization Algorithms....

(Will post on Complexity next week. I am waiting until the invited talks have their slides online so that I can point to them.) Let'...

Now that teaching has ended I plan to focus again on my P v NP book. I won't go on a full blog sabbatical, instead I'll aim to post ...

(I will post about CCC 2010 later in the week.) Several people have posted on the death of Martin Gardner: Complexity Blog (Lance) ...

(I will post about CCC 2010 later in the week.) The word Game is used in many different contexts within math and computer science. I li...

I called home last night and my daughter Molly had an exciting story to tell. She was at her friend Danielle's house (the same Molly and...

Tomorrow I'm off to Cambridge, MA for the 42nd Symposium on the Theory of Computing (STOC), the 25th Conference on Computational Comple...

In the latest CACM, Jilin Chen and Joseph Konstan analyze data from the ACM DL and conclude that low-acceptance rate conference have papers...

A reader from Mexico asks  I am a near-to-be graduate student from Computational Engineering. However, it wasn't what I expected from my...

Toronto Professor Avner Magen died in a climbing accident on Saturday. He's had a number of important  results on a variety of algorit...

The TV show 24 aired its last episode on May 24. The show used computers and technology ALOT, more than on most shows. Was it realistic? Wha...

Many of the various "proofs" of P≠NP follow a common theme: Define an NP problem with a certain structure. Argue that any algorith...

The 5th Conference on Logic, Computability and Randomness is going on this week at Notre Dame. Because of teaching and other commitments I ...