Computational Complexity

After my post on teaching PCPs, a reader questioned the wisdom of spending 6-8 lectures on PCP and asked what topics should be taught in an...

Dear Game Theorist/Computer Scientist: In keeping with our mission "to facilitate cross-fertilization between theories and applicatio...

Two very different articles in today's New York Times about battling the decline of interest in Chess. In the Op-Ed section, Jennifer Sh...

Chris Leonard, Elsevier editor of the CS theory journals is leaving Elsevier to be head of communities of the digital music service Digimpro...

Two years ago for the first time, I gave the proof of the PCP (Probabilistically Checkable Proof) theorem in my graduate complexity course. ...

The December 4th paper submission deadline for the Computational Complexity Conference in Prague is fast approaching. Get your papers ready...

When a scientist visits another university to give a seminar, someone gets assigned as host who during the talk introduces the speaker, make...

You attend the University of Chicago for three years, take a few years off and come back to finish your Bachelor's degree in Chemistry. ...

When we teach relativization, we often ask the class for a set A such that P A =NP A . The usual answers we get are an NP-complete A (which ...

As a Cornell University alum I get the occasional email from the president talking about the great things going on on the Ithaca campus. Tod...

Janos Simon gives a history of RAMs expanding on my recent Favorite Theorems post . A single paper is like a snapshot of the state of rese...

The acceptance rates at conferences for theoretical computer scientists tend to run higher than acceptance rates at conferences in other are...

Alice (not the real name) has a STOC submission with Bob and wanted to put the paper on a public archive. Bob insists that the paper not go ...

October Edition We end the list of favorite theorems from 1965-74 with two seminal papers by Cook and Reckhow. Stephen Cook and Robert R...

An excellent Chronicle article on negotiating your job offer. I fully agree with the article that you lose out considerably by not negotiat...

This notice came into my inbox last week. ChicTech, an outreach program of the University of Illinois Department of Computer Science, exten...

Welcome to ComplexityCast, the first of a very occasional podcast, an audio version of this weblog. First up, Bill Gasarch and I talk about...

A guest post by Rakesh Vohra. Fortnow's post on competitive ratio's has prompted a number to speculate on the `right' number ...

About a month ago I had the phone in my office removed. The number was one digit off from both maternity and a nurse's station at the U ...

When you cannot achieve the optimum solution of a problem, how do you measure the performance of an algorithm? If you knew the distribution ...