A natural scientist, data scientist, computer scientist, or curious person in general, will often end up with a hypothesis, and a yes-or-no question: Is my hypothesis true?

Some hypotheses are easy to test. To test the hypothesis My shoes are blue I only need to look down to determine the answer with near certainty. But interesting hypotheses are usually not so easy to test. For example:

- Are there at most 100,000 different species of fish in the ocean?

- I have a horribly-written written program A. Is it computing a linear function?

- I want to train a Support-Vector Machine to classify data, is it going to work?

- Is a certain gene X always passed on to a child?

- Does a social network graph contain a large clique?

These questions share an important feature: whereas I can determine whether my shoes are blue with certainty by directly observing all relevant information, in these latter examples it is impossible or infeasible to directly observe all relevant information. We can’t examine every single fish in the ocean, we can’t test a program on every input (or understand its behaviour from examination), we can’t generate every possible datum that we might want a machine classifier to classify. So what do we do?

The field of property testing studies these types of questions. In particular:

- How many random examples do I need to look at before I can report yes or no with high confidence?

- If I am allowed to make arbitrary queries to my object (my program, my graph, etc), does that help me make my decision faster?

- Can I make yes-or-no decisions more efficiently than I can approximate (or learn) the input? (For example, can I test if a Support-Vector Machine will work, more efficiently than simply running it and then verifying it on a test set?)

This course will introduce the basics of property testing.