Computational Complexity

We are looking for a postdoc to join the new CS Theory and Economics groups at Northwestern. We'll consider any theory candidates tho...

I deposited a check today at a new Chase ATM. You just put the check directly into the machine, the check gets scanned and the amount verifi...

In Yao's paper Should tables be sorted he did the following (I am paraphrasing alot). A (U,n;q)-WPDS (Word Probe Data Structure) for ...

I sometimes ask people What is your best paper? This question is actually ambigous. Here are criteria that you can use. Most importan...

Do you care about fonts? In other words do you care about how your paper looks? Not the details of the proofs or the quality of the exposit...

Guest Blog by Joe Kruskal . He is the Kruskal that did the MST algorithm, the Kruskal Tree Theorem and work on multidimensional scaling . H...

One of my crypto students pointed me to the "Nerdcore Hip-Hop" group MC Frontalot. Here's a trailer for their tribute film, N...

In the excellent paper On the power of two, three, and four probes It is well known that every graph with s vertices and at least 2s edg...

Sometimes the literature gives a proof, and then a reference, but the reference is not really to that proof. Here is an example. The theorem...

My younger daughter was deeply moved by An Inconvenient Truth and has become a staunch environmentalist ever since. She pushed me to change...

Recently the Kakeya Conjecture over finite fields (henceforth Kakeya ) was resolved. For information on what Kakeya is and how it was solved...

A few weeks ago Bill complained about how hard it is to get an electronic journal version of Barrington's theorem. Though Barrington...

TWO ITEMS: I) Reminder: STOC submission abstracts due today. II) New York Area Theory Day ...

Those of us who have taught logic to students are familiar with some of the fallacies they make: (1) confusing OR with XOR (reasonable given...

Michael Crichton passed away yesterday. His early novels and movies showing the potential dark sides of technology had a strong impact on m...

Random comments on the election. John McCain gave a nice concession speech and was excellent on SNL on Saturday. If he was that way the e...

I made a snapshot of the electoral markets map at 5 PM Central time Monday to compare to the actual votes. Meanwhile you can continue to wa...

I had my Graduate Class in Communication Complexity VOTE FOR PREZ in a secret ballot. The rules were: They could vote for anyone on the bal...

(Guest post from Rahul Santhanam) As promised, I did do a bit of experimenting this FOCS in terms of attending talks from other areas. He...

A hodgepodge of election stuff, in my last post before November 4. The markets and polls both suggest that the election is not that close...