Refine your search:

From Computational Complexity
#### Go Google Go

In 2009 I posted about a surprising new approach that moved computer Go from programs that lose to beginners to where it could beat good amateurs. That approach...

From Computational Complexity
#### We Still Can't Beat Relativization

As we celebrate our successes in computational complexity here's a sobering fact: We have had no new non-relativizing techniques in the last 25 years.
A little...

From Computational Complexity
#### The Growing Academic Divide

The decreases of the past three years bring the number of advertised jobs to a new low, below the level reached after the severe drop between 2007–08 and 2009...

From Computational Complexity
#### Rūsiņš Freivalds (1942-2016)

Rūsiņš Mārtiņš Freivalds passed away on Monday from a heart attack at the age of 73. I met Freivalds several times often through Carl Smith, who passed away himself...

From Computational Complexity
#### Complexity Year in Review 2015

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

From Computational Complexity
#### Guns and Crypto

“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 very few who pose a threat...

From Computational Complexity
#### Blog Followers

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. Details.

From Computational Complexity
#### Simons and Berkeley

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

From Computational Complexity
#### Ada Lovelace (1815-1852)

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 the basics of BASIC...

From Computational Complexity
#### Moonshots

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 and returning him safely to...

From Computational Complexity
#### Star Trek Computing

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 watched them each many times...

From Computational Complexity
#### A Silly String Theorem

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 was giving a talk on the...

From Computational Complexity
#### A Primer on Graph Isomorphism

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 also know Ryerson 251...

From Computational Complexity
#### George Boole (1815-1864)

George Boole, the father of symbolic logic, was born two hundred years ago today. His 1854 treatise, An investigation into the Laws of Thought, on Which are founded...

From Computational Complexity
#### S. Barry Cooper (1943-2015)

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

From Computational Complexity
#### Complexity Blast from the Past

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

From Computational Complexity
#### 2015 Fall Jobs Post

When the 2014 fall jobs post is our most popular post, you know it is time for the 2015 jobs post. This year instead of (or in addition to) posting your jobs in...

From Computational Complexity
#### Randomness by Complexity

Let n be the following number
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 ...

From Computational Complexity
#### Cancer Sucks

Karsten Schwan said the title quote when we were gathered as a faculty two years ago mourning the Georgia Tech School of Computer Science faculty member Mary...

From Computational Complexity
#### 21st Century Problems

My youngest daughter, Molly, a high school senior talking colleges with a woman about ten years her senior. The woman remembered all her friends watching the clock...