Refine your search:

From Computational Complexity
#### The Complexity of Rubik's Cube

In my book I use Rubik's Cube as an example of a puzzle we can computationally solve efficiently (as opposed to Sudoku or Rush Hour). How does this square with...

From Computational Complexity
#### 50 Years of the Turing Award

The ACM knows how to throw a party, a two-day celebration of the 50th anniversary of the Turing Award. Every recipient got a deck of Turing Award playing cards...

From Computational Complexity
#### Best. STOC. Ever.

The Panel on TCS: The Next Decade
Last week I attended STOC as its first new TheoryFest in Montreal. Pretty much everything about TheoryFest went extremely...

From Computational Complexity
#### Joan Clarke (1917-1996)

I'm in San Francisco for the ACM conference celebrating 50 years of the Turing Award. I'll post on STOC and the Turing award celebration next week. Today though...

From Computational Complexity
#### The Power of Economic Inefficiency

I grew up in a time when long distance domestic phone calls from AT&T costed $0.20/minute off peak ($1.30 in today's dollars). I also grew up close to AT&T Bell...

From Computational Complexity
#### Theory Jobs 2017

In the fall we point to theory jobs, in the spring we see who got them. Like last year and years past I created a fully editable Google Spreadsheet to crowd source...

From Computational Complexity
#### Who Sets Policy?

In April the New York Times Magazine ran an article Is it O.K. to Tinker with the Environment to Fight Climate Change? The article asks about the ethics of even...

From Computational Complexity
#### Graduation from the Other Side

I've attended many graduations in my time, mostly as faculty, a couple of times as a student or a brother. This last weekend I attended my first university...

From Computational Complexity
#### The Optimizers

Last week the Georgia Tech School of Industrial and Systems Engineering honored the 80th birthday of George Nemhauser and the 70th of Arkadi Nemirovski at an...

From Computational Complexity
#### William Tutte (1917-2002)

Today we celebrate our mothers of course, but also the 100th anniversary of the birth of Bill Tutte, best known for his role in decrypting the Lorenz cipher used...

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