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
How to Solve It
Today a guest post from Periklis Papakonstantinou, coincidentally not unrelated to Bill's post earlier this week. I'll be back with a special post on Sunday. I'm...
From Computational Complexity
Summer Conferences
Ahh summer. No Classes. Baseball. Opera Festivals. Time to focus on research and starting a new book. But, of course, many computer scientists travel the worldSTOC...
From Computational Complexity
So Was I
While Bill marched at the main March for Science in DC, I marched at the satellite march in Atlanta, my daughter Molly in Chicago, Scott Aaronson in Austin,in...
From Computational Complexity
Understanding Machine Learning
Today Georgia Tech had the launch event for our new Machine Learning Center. A panel discussion talked about different challenges in machine learning across the...
From Computational Complexity
Alice and Bob and Pat and Vanna
"The only useful thing computer science has given us is Alice and Bob" - A physicist at a 1999 quantum computing workshop Alice and Bob, great holders of secrets...
From Computational Complexity
A Bridge Too Far
In Atlanta last week a fire destroyed a major highway bridge right on my, and so many others, commutes. I've been playing with different strategies, like coming...
From Computational Complexity
Parity Games in Quasipolynomial Time
In one of the hallway discussions of last week's Dagstuhl I learned about an upcoming STOC paper Deciding Parity Games in Quasipolynomial Time by Cristian Calude...
From Computational Complexity
The Dagstuhl Family
This week I'm at the Dagstuhl workshop on Computational Complexity of Discrete Problems. As you long time readers know Dagstuhl is a German center that hosts...
From Computational Complexity
NP in ZPP implies PH in ZPP
If NP is in ZPP is the entire polynomial-time hierarchy in ZPP? I saw this result used in an old TCS Stackexchange post but I couldn't find a proof (comment ifharder...
From Computational Complexity
The Beauty of Computation
Lisa Randall wrote a New York Times book review of Carlo Rovelli's Reality Is Not What It Seems with some interesting responses. I want to focus on a single sentence...
From Computational Complexity
International Science
I did some counting and the 35 academic faculty members in the Georgia Tech School of Computer Science come from 14 different countries. My co-authors come from...
From Computational Complexity
Ken Arrow and Oscars Voting
Kenneth Arrow, the Nobel Prize winning economist known for his work on social choice and general equilibrium, passed away Tuesday at the age of 95. I can't cover...
From Computational Complexity
Liberatus Wins at Poker
Tuomas Sandholm (center) and Ph.D. student Noam Brown (via CMU) Congratulations to Liberatus the new poker champ. Liberatus, an AI program, beat several top-ranked...
From Computational Complexity
The Dichotomy Conjecture
Arash Rafiey, Jeff Kinne and Tomás Feder settle the Feder-Vardi dichotomy conjecture in their paper Dichotomy for Digraph Homomorphism Problems. Jeff Kinne is my...
From Computational Complexity
We Are All Iranians
A solidarity rally held at Georgia Tech today There are ten Iranian members of my department, the School of Computer Science at Georgia Tech, all of whom face...
From Computational Complexity
60 years of Eric and Mike
As I checked in at the Holiday Inn in New Brunswick Wednesday night, they asked me if I had stayed there before. I said it has been a while and they lookedWorkshop...
From Computational Complexity
Infinite Series and Markov Chains
There's a wonderful new series of math videos PBS Infinite Series hosted by Cornell Math Phd student Kelsey Houston-Edwards. Check out this latest video on Markov...
From Computational Complexity
Babai Strikes Back
"So it is quasipolynomial time again" Short Version: Babai fixed his proof. In November 2015 László Babai announced a talk "Graph Isomorphism in Quasipolynomial...
From Computational Complexity
Learning About Learning
Yesterday Scott Aaronson released his sweeping new P v NP survey. Babai gave an update on graph isomorphism, in short while he still has the first subexponential...
From Computational Complexity