# On searching for small Kochen-Specker vector systems

Joel Ouaknine ( Professor of Computer Science, Department of Computer Science, University of Oxford )

- 14:00 4th November 2011 ( week 4, Michaelmas Term 2011 )380

Kochen-Specker (KS) vector systems are sets of vectors in R^3 with the property that it is impossible to assign 0s and 1s to the vectors in such a way that no two orthogonal vectors are assigned 0 and no three mutually orthogonal vectors are assigned 1. The existence of such sets forms the basis of the Kochen-Specker and Free Will theorems. Currently, the smallest known KS vector system contains 31 vectors. I will describe some recent results on this problem, and in particular how we established a lower bound of 18 on the size of any KS vector system. I will also discuss a number of related theoretical questions, including some open problems.

(This is joint work with Felix Arends and Charles W. Wampler.)