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
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
Who Pays for Trips?
If Professor Alice at Faber College visits Dr. Bob at the University of Southern North Dakota, who should cover Alice's expenses? It depends on who does the asking...
From Computational Complexity
Birthday Paradox Variance
First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US. Here's an interesting approach to the birthday paradox...
From Computational Complexity
DIMACS at 20
Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event. DIMACS has served the theoretical computer science community well over these two...
From Computational Complexity
Citing Papers
A student asked me which version of a research paper to cite, a journal (the last reviewed version) or a conference (the first reviewed version) of a paper. I generally...
From Computational Complexity