Computational Complexity

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

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

The following story is not true nor has anyone claimed its true, but it has a point: A company gets a contract to do the following: train ...

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

I have posted about things I see in TV or Movies that are math or CS related: Do TV shows overestimate how much a genius can help solve cr...

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

Fireside chat with Dick Karp Above link is Samir Khuller interviewing Dick Karp, though its labelled as a fireside chat with Dick Kar...

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

(Sam Buss and Denis Hirschfeld helped me on this post.) I was reading the table of contents of the American Math Monthly and saw an artic...

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

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

A Pangram is a sentence that contains every letter of the alphabet The classic is:                                       The quick brown...

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

When the luddites smashed loom machines their supporters (including Lord Byron, Ada Lovelaces father) made two arguments in favor of the lu...

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

 (All of the math in this post is in here .) The following problem can be given as a FUN recreational problem to HS students or even youn...

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

Whenever I post on regular langs, whatever aspect I am looking at, I get a comment telling me that we should stop proving the pumping lemma ...

Unless you have hidden under a rock, you've heard that Amazon wants to build a second headquarters in or near a large North Americ...

Let EQ = {w : number of a's = number of b's } Let EQO = { a n b n : n ∈  N} (so its Equal and in Order) Typically we do the fo...