Communications of the ACM
Refine your search:
How the “Frontier” Became the Slogan of Uncontrolled AI
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration …
From Computational Complexity
The Pad
So I broke down and bought the iPad. Many people have asked whether the iPad is worth buying. The short answer: It will be.There are many many iPad reviews out...
From Computational Complexity
New Constructive Aspects of the Lov
Guest Post by Bernhard Haeupler The Lovász Local Lemma (LLL), slightly simplified, states that: Given a set of “bad” events, if for every event A there exists,...
From Computational Complexity
Choosing a Graduate School
Besides being tax day, Thursday is the deadline to decide where to attend graduate school. How should you choose? I've blogged on this topic before but a few recent...
From Computational Complexity
What Makes a Lecture "Distiguished"?
In January I gave a Distinguished Lecture in the CS Department at the University of Alberta. In early March I gave essentially the same lecture at Penn State in...
From Computational Complexity
Finding the Right Model
Last fall I wrote about the different focus on models and proofs in the Econ and CS theory communities. Today I'll focus on the purpose of a model and what makes...
From Computational Complexity
What Does It Meant to be Published?
I don't remember what prompted it but about a month ago I tweetedYour paper might appear on Arxiv or ECCC, be widely read and even well cited. But don't think that...
From Computational Complexity
SIGACT Social Networking
STOC conference and hotel registration now live. Early registration deadline is April 30th. Registration for Complexity and Electronic Commerce coming soon. You...
From Computational Complexity
Traveling Too Much
Three recent happenings made me think about the amount I travel.I hit the 50K club (Premier Executive) in United for the first time last year. At first I was excited...
From Computational Complexity
Laci Babai Turns 60
I'm at Ohio State for the Combinatorics, Groups, Algorithms, and Complexity Conference in honor of Laci Babai's 60th birthday. An incredible turn out with 74 talks...
From Computational Complexity
What I'm Doing Over Spring Break, Part I
It's spring break at Northwestern and as I write this Tuesday morning, I'm on a plane from San Francisco to Denver on my way to Columbus, Ohio. My kids have their...
From Computational Complexity
Notes to My Dad
My father Paul Fortnow passed away thirty years ago today. Five years ago I wrote about some of the lessons I learned from him. Suppose I could go contact him back...
From Computational Complexity
Unique Games Redux
With spring quarter arriving, I will take a break from book writing on P v. NP and come back to blogging. I hit my goal of getting past the point of no return (about...
From Computational Complexity
STOC and More
The Snows of Maryland are keeping Bill away from this blog again. Here in Chicago we deal with snow (and even earthquakes) in stride--my kids still have yet toaccepted...
From Computational Complexity
Sam Roweis (1972-2010)
Sam Roweis, an NYU CS professor specializing in machine learning, took his own life last Tuesday night. Jennifer Linden and Maneesh Sahani set up a weblog to share...
From Computational Complexity
2009 Complexity Year in Review
We go all the way back to January for the paper of the year, Mark Braverman's Poly-logarithmic independence fools AC0 circuits. Runners up include the Moser-Tardos...
From Computational Complexity
A Blog Sabbatical
With the end of the fall quarter I will take a break from the blog for a few months. This is not another End, just a chance to move my creative juices in another...
From Computational Complexity
Dequantification
After a talk on derandomization at Midwest Theory Day, someone asked if those techniques could also be used in quantum computing. In classical randomness under ...
From Computational Complexity
Complexity Vidcast 3
Quick announcement: If you are a student who wants to go to SODA but doesn't have the funds, click here. I had forgotten we did this. Here's a video of my daughter...
From Computational Complexity
The Probability of P=NP
Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P?NP (if it's independent it's still equal or unequal in...
From Computational Complexity