7

In 1996 Papadimitriou and Yannakakis noted that there exists an $n^{O(\log n)}$ brute-force algorithm (where $n$ is the size of the input) for computing VC-dimension of a 0-1 matrix by checking all the subsets of size up to the trivial bound, the logarithm of the number of hypotheses. Manurangsi and Rubinstein later showed this bound basically cannot be ...


Only top voted, non community-wiki answers of a minimum length are eligible