Refine your search:

From Computational Complexity
#### A Sensitive Game

Last month I posted about the sensitivity conjecture and today I would like to talk about an interesting game developed by Gilmer, Koucký and Saks and independently...

From Computational Complexity
#### Donald Knuth Turns Eighty

We've kept this blog going long enough that we start repeating our celebrations. Ten years ago Bill celebrated Don Knuth's 70th Birthday and today Donald Knuthcelebrates...

From Computational Complexity
#### Complexity Year in Review 2017

Theorem of the year goes to the resolution of the dichotomy conjecture. I wrote about the conjecture in February and while the Feder et. al paper didn't hold up...

From Computational Complexity
#### Having Faith in Complexity

I believe P ≠ NP as much as anyone else. Nevertheless should we worry about trust we put in complexity?
You don't need the full power of P = NP to break cryptography...

From Computational Complexity
#### Our AI future: The good and the Ugly

I don’t directly work in machine learning but one cannot deny the progress it has made and the effect it has on society. Who would have thought even a few years...

From Computational Complexity
#### Razor's Edge

Informally the sensitivity conjecture asks whether every hard Boolean function has a razor's edge input, where flipping a random bit has a reasonable chance ofrecent...

From Computational Complexity
#### Kolmogorov Complexity and the Primes

Bill's post on how to derive the non-finiteness of the primes from Van der Waerden's theorem reminds me of a nice proof using Kolmogorov complexity.
A quick primer...

From Computational Complexity
#### The Grad Student Tax

By now as you've read from Luca or Scott or PhD Comics or a variety of other sources on the dangerous changes to the tax code that passed the US House of Representatives...

From Computational Complexity
#### A Tale of Three Rankings

In the Spring of 2018 the US News and World Report should release their latest rankings of US graduate science programs including computer science. These are the...

From Computational Complexity
#### Advice for the Advisor

A soon-to-be professor asked me recently if I could share some ideas on on how to advise students. I started to write some notes only to realize that I had already...

From Computational Complexity
#### Matching and Complexity

Given a group of people, can you pair them up so that each pair are Facebook friends with each other? This is the famous perfect matching problem. The complexity...

From Computational Complexity
#### 2017 Fall Jobs Post

You're finishing up grad school or a postdoc and ask yourself what should I do for the rest of my life? We can't answer that for you but we can help you figureCRA...

From Computational Complexity
#### The Amazon Gold Rush

Unless you have hidden under a rock, Amazon wants to build a second headquarters in or near a large North American city. Amazon put out a nice old fashioned...

From Computational Complexity
#### Lessons from the Nobel Prizes

We've had a big week of awards with the Nobel Prizes and the MacArthur "Genius" Fellows. The MacArthur Fellows include two computer scientists, Regina Barzilay and...

From Computational Complexity
#### Monty Hall (1921-2017) and His Problem

Monty Hall passed away yesterday, best known for co-creating and hosting the game show The Price is Right, a show I occasionally watched as a kid. To the best...

From Computational Complexity
#### Tragic Losses

I'd like to remember two young people who's lives were taken way too early. I didn't know either well but both played large roles in two different communities...

From Computational Complexity
#### Random Storm Thoughts

It's Monday as I write this post from home. Atlanta, for the first time ever, is in a tropical storm warning. Georgia Tech is closed today and tomorrow. I'm just...

From Computational Complexity
#### Rules and Exceptions

As a mathematician nothing grates me more than the expression "The exception that proves the rule". Either we bake the exception into the rule (all primes are odd...

From Computational Complexity
#### NOT So Powerful

A monotone circuit has only AND and OR gates, no NOT gates. Monotone circuits can only produce monotone functions like clique or perfect matching, where addingFavorite...

From Computational Complexity
#### Kurtz-Fest

Stuart Kurtz turned 60 last October and his former students John Rogers and Stephen Fenner organized a celebration in his honor earlier this week at Fenner's...