Computational Complexity

We had an incredible year for theorems in 2015, the strongest year in computational complexity in the last decade. Topping the list as the t...

“We believe it would be wrong to weaken security for hundreds of millions of law-abiding customers so that it will also be weaker for the ve...

If you follow this or any other Blogger-based blog via a non-Google account, you'll need to follow with a Google account instead. Detail...

The  Simons Institute for the Theory of Computing  in Berkeley held two programs this fall, Fine-Grained Complexity and Algorithm Design  an...

Back in my teens I had ordered my first computer, a TRS-80 from Radio Shack, and I grew anxious in the weeks before it arrived. I learned ...

In the same week I got email claming: 1) Babai had shown that GI is in quasipoly time. 2)  Opeyemi Enoch, a Nigerian Mathematician, sol...

In 1961 Kennedy said "this nation should commit itself to achieving the goal, before this decade is out, of landing a man on the Moon a...

I went to an AMS conference with my High School Student Naveen (who presented  this paper)  and an ugrad from my REU program Nichole (who pr...

In the wake of Leonard Nimoy's death last February, I decided to rewatch the entire original Star Trek series, all 79 episodes. I had wa...

First a note on a serious theorem: Babai has posted a video  (mp4, 1h 40 m, 653MB) of his first talk on his Graph Isomorphism algorithm. I ...

I've seen the word `civilians' expanded in use from non-military to non-X for some X. Not sure I've ever seen `civilians' m...

I spent 14 years on the faculty at the University of Chicago. I know László Babai well, we collaborated on some of my best known work. I ...

As you all know Laszlo Babai will give a talk Tuesday Nov 10 on a result: GI in  quasipolynomial time (2 to a polylog). Other theory blogs h...

The theory blogosphere is atwitter with an announcement of a talk next Tuesday at Chicago by László Babai  Graph Isomorphism in Quasipolyn...

 (In honor of Boole's Birthday yesterday see this.) I recently (Oct 2 and 3 2015) went to a conference on Computation and Journalism (...

George Boole , the father of symbolic logic, was born two hundred years ago today. His 1854 treatise,  An investigation into the Laws of T...

Barry Cooper , a computability theorist and professor at the University of Leeds, passed away on Monday after a brief illness. Cooper was ...

About 20 years ago I went to a talk by Jim Propp on the fractional chromatic number of a graph. ( Here is a link to a free legal copy of t...

My friend Marty in grad school mysteriously disappeared in 1985 and showed up yesterday looking exactly the same as I remember him. He said ...

I have always wondered why YELP and Amazon Reviews and other review sites work as well as they do since a company COULD flood one with false...