Computational Complexity

For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers. Recall that from the work comi...

Leonard Cassuto writes in the Chronicle an article  Ph.D. Attrition: How Much Is Too Much?  He presupposes the answer with the subtitle ...

In a a prior post I suggested that STOC perhaps have people give posters instead of talks. While I doubt this will ever happen I think its ...

In a prior post I tried to give a simple example of a proof that uses Gen Functions where there was no other way to do it. For better or w...

Recall from my last post: PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on ...

I have (1) a math problem to tell you about (though I suspect many readers already know it), (2) a story about it, and (3) a point to make. ...

(This blog is based on things I heard at the Erdos 100th Bday Conference ) I have spend the last week at the Erdos 100th bday conference. ...

Today Yahoo is closing AltaVista, the best search engine before Google. The news caught me by surprise, AltaVista still existed? A number of...

Bill and I are both in Europe this week. I'm in Milan at  Computability in Europe and Bill is 500 miles away in Budapest for the  Paul ...

The AAA foundation measured cognitive distraction while driving and reported that having a passenger in the car is as dangerous as using a ...

Ronald de Wolf gave a GREAT talk at CCC on the uses of Quantum techniques to Classical Problems. He made the analogy of using the Prob Meth...

An economist friend asked me if there were still productivity gains to be had for office workers (like us). After all, we have email, social...

For each of these, are they frauds? The Turk was a chess playing ``computer'' (around 1770) that was later discovered to be chea...

Last weekend I took my teenage daughters to see The Internship , the Vince Vaughn-Owen Wilson vehicle where they play two forty-year old int...

At the STOC business meeting Joan Feigenbaum (PC chair) raised some very good points. There was no real discussion (or perhaps the burning ...

Lance:  Welcome to another exciting typecast coming from sunny Stanford University. I'm with Bill at the 28th Conference on Computationa...

Bill and I are in Palo Alto this week for the co-located meetings of STOC and Complexity . In a new ACM policy, the STOC 2013 papers  are f...

Lots of talk, mostly negative , about the proposed  High Quality Research Act . Prior to making an award of any contract or grant funding ...

Time for the annual spring jobs posts. Like last year , I set up a  Google Spreadsheet  that everyone can edit so we can crowd source who is...

I just read two very different science books, Daniel Kahneman's Thinking, Fast and Slow and Scott Aaronson's Quantum Computing sinc...