Refine your search:

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

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

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

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

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

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

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

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

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

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

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