Blogroll | Communications of the ACM

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

From Computational Complexity

STOC Business Meeting

This week I'm at the Federated Computing Research Conference in Portland, a collection of many mostly ACM conferences. Last night was the STOC business meeting.... Lance Fortnow
From Computational Complexity | June 16, 2015 at 04:53 PM

From Computational Complexity

A Metric Group Product

A guest post by Dylan McKay, recently graduated from Georgia Tech and soon to be PhD student at Stanford. Here a cute puzzle motivated by a pair of undergrads... Lance Fortnow
From Computational Complexity | June 11, 2015 at 08:37 AM

From Computational Complexity

Award Season

László Babai will receive the 2015 Knuth Prize and Daniel Spielman and Shang-Hua Teng will receive the 2015 Gödel Prize. ACM issued a press release for both... Lance Fortnow
From Computational Complexity | June 1, 2015 at 04:46 PM

From Computational Complexity

John Nash (1928-2015)

John Nash and his wife Alicia died in a taxi accident, returning from the airport after he received the Abel prize in Norway. The public knew John Nash as the "Beautiful... Lance Fortnow
From Computational Complexity | May 25, 2015 at 10:56 AM

From Computational Complexity

Theory Jobs 2015

In the fall we list theory jobs, in the spring we see who got them. Like last year, I created a fully editable Google Spreadsheet to crowd source who is going where... Lance Fortnow
From Computational Complexity | May 18, 2015 at 08:24 PM

From Computational Complexity

Fiftieth Anniversary of the Publication of the seminal paper on Computational Complexity

Juris Hartmanis and Richard Stearns in a photo dated May 1963. The main theorem from their paper is on the board later improved by Hennie and Stearns. Photo courtesy... Lance Fortnow
From Computational Complexity | May 14, 2015 at 09:34 AM

From Computational Complexity

The Virtuous Cycle

Last week we have a celebration of the new CS graduates at Georgia Tech where each graduating student says what their plans are for next year. Other than the few... Lance Fortnow
From Computational Complexity | May 7, 2015 at 07:30 AM

From Computational Complexity

Is Logarithmic Space Closed Under Kleene Star?

A Georgia Tech student asked the title question in an introductory theory course. The instructor asked his TA, the TA asked me and I asked the oracle of all things... Lance Fortnow
From Computational Complexity | April 29, 2015 at 07:50 PM

From Computational Complexity

Fifty Years of Moore's Law

Gordon Moore formulated his famous law in a paper dated fifty years and five days ago. We all have seen how Moore's law has changed real-world computing, but how... Lance Fortnow
From Computational Complexity | April 24, 2015 at 07:20 AM

From Computational Complexity

PH Infinite Under a Random Oracle

Benjamin Rossman, Rocco Servedio and Li-Yang Tan show new circuit lower bounds that imply, among other things, that the polynomial-time hierarchy is infinite relative... Lance Fortnow
From Computational Complexity | April 16, 2015 at 09:14 AM

From Computational Complexity

Baseball is More Than Data

As baseball starts its second week, lets reflect a bit on how data analytics has changed the game. Not just the Moneyball phenomenon of ranking players but also... Lance Fortnow
From Computational Complexity | April 14, 2015 at 01:01 PM

From Computational Complexity

FCRC 2015

Every four years the Association for Computing Machinery organizes a Federated Computing Research Conference consisting of several co-located conferences and some... Lance Fortnow
From Computational Complexity | April 9, 2015 at 07:12 AM