Refine your search:

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...

From Computational Complexity
#### A Few Interesting Computer Science Papers

Probabilistic Rank and Matrix Rigidity by Josh Alman and Ryan Williams
Leslie Valiant outlined an approach to proving circuit lower bounds from matrix rigidity...

From Computational Complexity
#### Music Theory for Theorists

I fully completed and passed my first MOOC, Fundamentals of Music Theory, a Coursera course out of the University of Edinburgh. I played the tuba in college and...