Refine your search:

From Computational Complexity
#### Amir Pnueli (1941-2009)

Amir Pnueli, an expert in temporal logic and program verification who won the 1996 Turing Award, passed away Monday from a brain hemorrhage. His colleague Lenore...

From Computational Complexity
#### FOCS News

Last month I suggested that students should go to FOCS even if they didn't have a paper there. I doubt my post had much to do with it, but I heard FOCS did attract...

From Computational Complexity
#### Proud to be a Monomath

A girl told her father that history was much easier when he was in school. "Why?" he asked. She responded "Because there was so much less of it."
An old joke, but...

From Computational Complexity
#### FOCS Last Day

Last (but surely not least) day at FOCS 09!Jan Vondrak talked about some nice results that unify previous query complexity approaches in proving lower bounds for...

From Computational Complexity
#### FOCS Day 2

After an early morning injection of much needed caffeine, Team Northwestern was ready for the next round of talks. Today's program consisted of talks more related...

From Computational Complexity
#### FOCS Day 1

Michele and Michael continue their guest posts from Atlanta.The first day of FOCS is officially over. 8 sessions, 26 talks and 270 proceedings pages have already...

From Computational Complexity
#### FOCS Day 0

Alas, I'm not in Atlanta but in New York City for another meeting. Something different this time--FOCS through the eyes of two Northwestern students, Michele Budinich and...

From Computational Complexity
#### The Humbling Power of P v NP

[Note from Bill: He now has an on-line list of papers who still need reviewers]
Noam Nisan, back in grad school in the 80's made the following suggestion...

From Computational Complexity
#### Typecasting Again

Lance: Welcome to our second typecast on the last full day of Dagstuhl. I may not see Bill for a while so we'd thought we'd get in one more chat before we go our...

From Computational Complexity
#### Thanks for the Fuzzy Memories

In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold function then P = NP. Their...

From Computational Complexity
#### Bill and Lance's Excellent German Adventure

Lance: Because we don't have a good microphone, Bill and I decided to have our first typecast. Hi Bill.
Bill: Hi Lance. We'll be typecast SUPERSTARS.
...

From Computational Complexity
#### Dagstuhl Day One

The talks Monday were after my own heart. The day started with relativization: The always entertaining Scott Aaronson talked on his approach to get an oracle where...

From Computational Complexity
#### The Molly Solution

This week Bill and I are both at the Dagstuhl Workshop on Algebraic Methods in Computation Complexity. I'll try to cover some of the talks and discussions on the...

From Computational Complexity
#### Complexity Vidcast 2

Bill and I battle it out over what should be taught in a complexity course in our new vidcast.

From Computational Complexity
#### Publicity for P versus NP

On the New York Times website, John Markoff writes an article Prizes Aside, the P-NP Puzzler has Consequences motivated by my CACM article on The Status of the....

From Computational Complexity
#### On Being Narrow

In a tweet a few days ago, David Bacon
wonders why everyone always assumes all he can do is quantum computing? Oh, because that's all he's done. Time to do something...

From Computational Complexity
#### The IT Rules

My family has discovered a British Series, the IT Crowd, about two techies in a corporate IT department. An American version never got past the pilot phase.
...

From Computational Complexity
#### Inspiring a Love of Math

A reader writes
I come to you by way of your computational complexity blog. I get that there is some really good stuff there, but frankly don’t understand about...

From Computational Complexity
#### The Netflix Prize and the Sequel

Nearly three years ago I posted on the just announced Netflix prize. First to a 10% increase in the quality of the movie recommendations would receive a million...

From Computational Complexity
#### Why You Shouldn't Not Go to FOCS

You can now register on-line for FOCS which includes the 50th celebration. Early registration deadline is October 1. Hotel rate good until October 9th or whilehttp...