# People tend to get the Turing Test slightly wrong

Now I’m not a philosopher myself, and I’m not necessarily that interested in AI per se, but whenever I hear people talk about the Turing test, there’s a good chance that they’re not talking about it quite right – I think.
Turing does not say: you have to be able to win this game in order to be intelligent. He does not say that something or someone is intelligent if and only if they pass the test.…

Read more ⟶
# Slack Variables (or: All Variables are Slack Variables?)

Now a lot of maths and computer science is about reductions to systems that are somehow restricted and therefore easier to work with, right? Like how any logical formula can be put in conjunctive normal form, or how you can make all logical operators from NAND; how there’s row echelon form for systems of linear equalities and standard form for linear programs.
Here’s a fun one that lies at the heart of the simplex algorithm: slack form.…

Read more ⟶
# Dual Spanning Trees in a Planar Graph

Now planar graphs have a dual, right? Make a vertex for every face and an edge between them if the two faces are adjacent. (Don’t forget the outer face.) Here’s a fun construction: take a spanning tree $T$ in the original graph and consider those edges impassible for the dual – that is, don’t consider the faces adjacent in the dual if the edge between them is in $T$. Call what remains of the dual graph $D$: I claim $D$ is in fact a spanning tree of the dual.…

Read more ⟶
# Don't Connect the Data Points on your Scatterplots

Now today, please permit me to rant for a second about connecting the dots when you plot data. Stop it! I mean, probably. Ask yourself: “does it make sense to interpolate these data points?” The answer is probably “no” and you should just do a scatterplot with individual points.
There are counterexamples: maybe you plot an ROC curve for a binary classifier. It is literally possible take linear combinations of classifiers to get the interpolated properties.…

Read more ⟶
# Strong and Weak NP-Hardness

In a previous post I talk about how NP-hardness doesn’t necessarily mean you can’t solve a problem. There are degrees to which this is true or not in practice, but there is also a distinction we can make at the level of complexity theory.
Consider the KNAPSACK problem with $n$ items and maximum weight $W$. There is a famous dynamic program for this with runtime order of $n\cdot W$. That looks polynomial, isn’t Knapsack NP-hard?…

Read more ⟶