Blogroll | Communications of the ACM

From Computational Complexity

Changing This Ancient Art Into a Science

The ACM announced yesterday that they will award the 2015 Turing Award to Whitfield Diffie and Martin Hellman for contributions to modern cryptography. The Turing... Lance Fortnow
From Computational Complexity | March 2, 2016 at 08:46 AM

From Computational Complexity

Primary Game Theory

[Nominations open for the SIGACT Distinguished Service Prize. Deadline: April 1] The US presidential primaries have not gone as expected as you can see from the... Lance Fortnow
From Computational Complexity | February 25, 2016 at 08:05 AM

From Computational Complexity

Posting Papers

In the ancient days of the 80's, if someone wanted a paper from you, they would ask and you would mail via post. Sometimes I would get a self-addressed envelope... Lance Fortnow
From Computational Complexity | February 18, 2016 at 07:33 AM

From Computational Complexity

The Moral Hazard of Avoiding Complexity Assumptions

Moshe Vardi's CACM editor letter The Moral Hazard of Complexity-Theoretic Assumptions practically begs a response from this blog. I also encourage you to read the... Lance Fortnow
From Computational Complexity | February 8, 2016 at 04:56 PM

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... Lance Fortnow
From Computational Complexity | February 4, 2016 at 07:20 AM

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... Lance Fortnow
From Computational Complexity | January 28, 2016 at 08:30 AM

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... Lance Fortnow
From Computational Complexity | January 21, 2016 at 06:26 AM

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... Lance Fortnow
From Computational Complexity | January 6, 2016 at 12:58 PM

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... Lance Fortnow
From Computational Complexity | December 28, 2015 at 11:09 AM

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... Lance Fortnow
From Computational Complexity | December 22, 2015 at 09:58 AM

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. Lance Fortnow
From Computational Complexity | December 21, 2015 at 10:12 AM

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... Lance Fortnow
From Computational Complexity | December 16, 2015 at 03:00 PM

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... Lance Fortnow
From Computational Complexity | December 10, 2015 at 08:17 AM

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... Lance Fortnow
From Computational Complexity | December 3, 2015 at 09:43 AM

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... Lance Fortnow
From Computational Complexity | November 23, 2015 at 10:30 AM

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... Lance Fortnow
From Computational Complexity | November 19, 2015 at 08:53 AM

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... Lance Fortnow
From Computational Complexity | November 12, 2015 at 08:30 AM

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... Lance Fortnow
From Computational Complexity | November 2, 2015 at 05:52 AM

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... Lance Fortnow
From Computational Complexity | October 29, 2015 at 07:38 AM

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 ... Lance Fortnow
From Computational Complexity | October 22, 2015 at 07:55 AM