computationalcomplexity

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for...

(All references in this blog post can be found in the main article the post is about which is here.)

Recall that \(R(s,k)  \) is the least \(n\) so that, for all 2-colorings of the edges of \(K_n\), there is either a RED \(s\)-clique or a BLUE \(k\)-clique.

\(R(k,k...

Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road, a network of trading routes across Asia active from the second century BCE until the mid-15th century. I knew of the Silk Road but was surprised by how much it used and fostered various t...

A mnemonic device is a sentence where the first letters of the words are helpful to remember something. My favorite one is

                              My Very Educated Mother Just Said Uh, No Pluto

You probably know what it's for. If not you can type it into Googl...

There are two ways to look at the P v NP problem, as a formal mathematically defined conjecture as a Clay Millennium Prize Problem, and as the more intuitive notion that everything efficiently verifiable is efficiently computable and the implications that has on our ability to compute.

I've