Computational Complexity

Earlier this month the New York Times had a story  Computer Studies Made Cool, on Film and Now on Campus  followed-up on a series of short e...

MATH ON TV FUTURAMA mentions the Banach-Tarski Paradox! In the June 23, 2011 episode Professor Farnsworth invents a Banach-Tarski-Dupla-S...

(A workshop on Coding, Complexity and Sparsity will be held at Ann Arbor, August 1-4, 2011. See this website .) More thoughts on FCRC. ...

We redesigned the blog to use the newest Blogger features. This lets me not have to maintain the 2002 html code we had before and lets us ha...

Email celebrates its fortieth anniversary  so let me tell the story of my job for three summers, and part-time during the academic year, whi...

In 2002 I did a poll that appeared as SIGACT News Complexity Theory Column 36 on what people thought of P vs NP. See here . That articl...

The computer science job market never comes to a complete close. CI Fellows are still being decided, Oxford is just starting its search for...

I do not log on at conferences so I came back to 400 emails. Exactly 400- not sure how I managed that. TODAY I am posting about a few things...

The newly renamed Computational Complexity Channel  features two new vidcasts Bill and I hosted last Thursday from San Jose. Bill's ...

The Complexity conference comes to a close today and I head back to Chicago. I tend to go to few talks, preferring hallway conversations, bu...

Russell Impagliazzo gave a talk at Complexity about his five worlds . We didn't know whether Heuristica and Algorithmica were different,...

Tuesday at FCRC. 7 AM: A grad student at Northwestern administers my final exam at 9 AM Chicago time. He has my mobile number just in case...

In my role as SIGACT chair, I got to attend the ACM Awards Banquet held at the beginning of FCRC in San Jose. I shared a table with Mitzenm...

One last Molly post for the end of the school year. Tomorrow is her birthday and I enter that moment I have been dreading for the past thirt...

I was at RatLoCC last week which stands for Ramsey Theory in Logic, Combinatorics and Complexity . The idea was to bring in researchers for...

As Lipton  and Felten  note, today is the 75th anniversary of Turing's  On Computable Numbers, With an Application to The Entscheidungsp...

Most of you are familiar with the research that using a cell phone is just as dangerous as driving drunk. Method: We used a high-fidelit...

Back in 2005 I worried about loss of excitement about computer science among America's youth. Today computers have become almost as c...

The 2011 Gödel Prize is awarded to Johan T. Håstad for his paper: Some optimal inapproximability results , Journal of the ACM, 48: 798--8...

Cambridge Press (and others) offers PRINT-ON-DEMAND for some books. This is a guest post by Lauren Cowles from Cambridge Books about this, a...