Blogroll | Communications of the ACM

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

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

From Computational Complexity

Randomness by Complexity

Let n be the following number 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 ... Lance Fortnow
From Computational Complexity | October 7, 2015 at 08:53 AM

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... Lance Fortnow
From Computational Complexity | October 1, 2015 at 12:48 PM

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... Lance Fortnow
From Computational Complexity | September 24, 2015 at 08:23 AM

From Computational Complexity

The Theorems Conference

All too often theoretical computer scientists get more obsessed by proofs than the theorems themselves. I suggest a theorems conference. Here's how it would work... Lance Fortnow
From Computational Complexity | September 17, 2015 at 03:49 AM

From Computational Complexity

Designer Chips

A computer architecture researcher talked to me about a role theoretical computer science can play for them: creating a new kind of computer processor. Microprocessors... Lance Fortnow
From Computational Complexity | September 10, 2015 at 10:23 AM

From Computational Complexity

Whiplashed

I recently watched the movie Whiplash, about a college jazz band director, Fletcher played by J.K. Simmons, who torments his musicians to force them to be their... Lance Fortnow
From Computational Complexity | September 3, 2015 at 04:01 PM

From Computational Complexity

PACM

I serve on the conference committee of the ACM publications board and we've had extensive discussions on the question of the role of journals in publication venues... Lance Fortnow
From Computational Complexity | August 27, 2015 at 08:01 AM

From Computational Complexity

Crowdsourcing the Truth

A new project Augur aims to create a decentralized prediction market. If this post so moves you, Augur is in the midst of a reputation sale. Don't miss out if you... Lance Fortnow
From Computational Complexity | August 20, 2015 at 08:18 AM

From Computational Complexity

What is Theoretical Computer Science?

Moshe Vardi asks a provocative question in Windows on Theory and CACM: "Why doesn't ACM have a SIG for Theoretical Computer Science?" The reaction of myself and... Lance Fortnow
From Computational Complexity | August 13, 2015 at 08:45 AM

From Computational Complexity

New Proof of the Isolation Lemma

The isolation lemma of Mulmuley, Vazirani and Vazirani says that if we take random weights for elements in a set system, with high probability there will be a unique... Lance Fortnow
From Computational Complexity | July 23, 2015 at 09:07 AM

From Computational Complexity

Microsoft Faculty Summit

Last week I participated in my first Microsoft Faculty Summit, an annual soiree where Microsoft brings about a hundred faculty to Redmond to see the latest in Microsoft... Lance Fortnow
From Computational Complexity | July 16, 2015 at 08:40 AM

From Computational Complexity

Will Our Understanding of Math Deteriorate Over Time?

Scientific American writes about rescuing the enormous theorem (classification of finite simple groups) before the proof vanishes. How can a proof vanish? In mathematics... Lance Fortnow
From Computational Complexity | July 9, 2015 at 09:53 AM

From Computational Complexity

Goodbye SIGACT and CRA

Tuesday I served my last day on two organizations, the ACM SIGACT Executive Committee and the CRA Board of Directors. I spent ten years on the SIGACT (Specialbig... Lance Fortnow
From Computational Complexity | July 2, 2015 at 07:56 AM

From Computational Complexity

Changing STOC

At the recently completed STOC and the previous FOCS, much of the discussion revolved around reforming the conferences. You read the discussion and comments onarXiv... Lance Fortnow
From Computational Complexity | June 25, 2015 at 08:33 AM

From Computational Complexity

FCRC Complexity

On Wednesday at FCRC, the Complexity, STOC and EC (Economics and Computation) conferences all have sessions, a smorgasbord of talks, but tough decisions on what... Lance Fortnow
From Computational Complexity | June 18, 2015 at 12:59 PM