Refine your search:

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
#### Complexity Year in Review 2016

Paper of the year goes to A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents by Haris Aziz and Simon Mackenzie. Might not seem like...

From Computational Complexity
#### Hidden Figures

Yesterday in our tradition of seeing math movies on Christmas, we saw Hidden Figures, the story of African-American women who worked as "computers" at NASA in...

From Computational Complexity
#### Moneyball for Academics

MIT and Tel Aviv business school professors Dimitris Bertsimas, Erik Brynjolfsson, Shachar Reichman and John Silberholz wrote an intriguing paper Tenure Analytics...

From Computational Complexity
#### Freedom of Speech

Bill and I have always strongly believed in the principle of freedom of speech, guaranteed to us by the constitution of the United States. The government block...

From Computational Complexity
#### Fixing the Academic Job Market

Last month I posted about the craziness of the computer science academic job market due mainly to the decentralized nature of our field. Here are some ideas ofSingle...