Blogroll | Communications of the ACM

From Computational Complexity

A Prayer Book for the Internet Generation

As a young kid in the Reform Jewish community we used the Union Prayer Book, a traditional book with Hebrew on the right and English on the left with lots of instructions... Lance
From Computational Complexity | November 17, 2009 at 01:11 PM

From Computational Complexity

Jobs

As many university's still feel the effect of the financial crises, many have limited or no positions to hire new tenure-track faculty so I expect the academicUniversity... Lance
From Computational Complexity | November 13, 2009 at 11:54 AM

From Computational Complexity

Breaking Walls

Many of you readers don't remember a time when there were two Germanys or when we didn't think IP = PSPACE. Two walls collapsed in November of 1989 that changed... Lance
From Computational Complexity | November 12, 2009 at 11:36 AM

From Computational Complexity

Button Button

Here is the offer: If you press the button you will receive $200,000. The caveat: Someone you don't know will die. I was born during run of the original Twilight... Lance
From Computational Complexity | November 6, 2009 at 01:29 PM

From Computational Complexity

Innovation

The new Innovations in Computer Science conference announced their accepted papers earlier this week including my paper with Rahul Santhanam "Bounding Rationality... Lance
From Computational Complexity | November 5, 2009 at 12:29 PM

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... Lance
From Computational Complexity | November 4, 2009 at 11:44 AM

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... Lance
From Computational Complexity | October 30, 2009 at 09:35 AM

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... Lance
From Computational Complexity | October 29, 2009 at 10:41 AM

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... Lance
From Computational Complexity | October 28, 2009 at 11:06 AM

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... Lance
From Computational Complexity | October 27, 2009 at 10:26 AM

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... Lance
From Computational Complexity | October 26, 2009 at 10:20 AM

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... Lance
From Computational Complexity | October 25, 2009 at 10:39 PM

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... Lance
From Computational Complexity | October 21, 2009 at 10:57 AM

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... Lance Fortnow
From Computational Complexity | October 16, 2009 at 09:41 AM

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... Lance
From Computational Complexity | October 15, 2009 at 04:59 PM

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. ... Lance
From Computational Complexity | October 14, 2009 at 05:12 PM

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... Lance
From Computational Complexity | October 13, 2009 at 11:34 AM

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... Lance
From Computational Complexity | October 12, 2009 at 05:12 PM

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. Lance
From Computational Complexity | October 9, 2009 at 05:14 PM

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.... Lance
From Computational Complexity | October 8, 2009 at 05:14 PM