Computational Complexity

(True Story, but names are changed for no good reason.) Alice, Bob, and Carol are betting on who will be the Republican Nominee in 2016. ...

In a prior post ( here ) I discussed the change problem: given a dollar, how many ways can you make change using pennies, nickels, dimes, an...

I have been the SIGACT NEWS book review editor since 1997. I have tried to get about 10 books reviewed per column. I have succeeded- perhaps...

This week I'm at the CRA Snowbird conference , the biennial meeting of CS chairs and other leaders in the field. In 2012  many of the di...

New York Times, dateline June 11, 2019 With a near record-setting investment announced last week, the self-driving car service Elfdrive ...

In my last post I asked for candidates for names for the top and bottom part of (n choose k) . Here are the candidates and my comments on th...

Consider the sequence: x/y,  (x+1)/y, (x+2)/y, ..., (x+z)/y one could say  in this sequence of fractions the numerators goes through z-1...

Not only did Moser give a near optimal construction, but he did so in my favorite STOC talk of the decade. A Constructive Proof of the Lo...

I just returned from visiting my former student Rahul Santhanam in Edinburgh. The National Museum of Scotland has an  exhibit  on logarith...

Last week fortune smiled on two of my friends: Ken Regan made the cover of Chess Life for his work on catching chess cheaters. (See here....

My brother went through his old stuff cleaning out his apartment in New York and stumbled upon the 1981 computer dating questionnaire I wrot...

(For a related post see  my post on Schur's theorem . The paper THIS post refers to is  here .) (ADDED LATER: A commenter pointed to G...

The famous Probabilistically Checkable Proof Theorem due to Arora, Lund, Motwani, Sudan and Szegedy states that every problem in NP has a p...

Talking about Graphi Isom with some students they came up with the following idea which is certainly not new; however, I couldn't quite ...

I'm returning from the 2014 IEEE Conference on Computational Complexity in Vancouver, unfortunately missing the last day. Several very ...

In honor of the 100th anniversary of the birth of Wassily Hoeffding  today, let's recall his incredibly useful inequality . Prob(|X-p...

The following problem was on my final for Formal Lang theory (Reg, P, NP, Dec, c.e.) For this problem you may assume P\ne NP and NP\ne coN...

The steering committee for the CCC recently announced its decision to be independent of IEEE. Here  is their open letter to that effect. I...

At the just completed STOC conference I received the 2014  SIGACT Distinguished Service Prize . Part of this citation reads"His blog, ...

The law of small numbers is that there are not enough small numbers for all of the tasks that are assigned to them. That makes some math cra...