6
$\begingroup$

Let $F$ be a class of subsets of a finite set $X$ of cardinality $n$. What is the complexity of computing the VC dimension of $F$? Can we do better than looping through every subset of $X$ and checking if $F$ shatters it?

$\endgroup$

1 Answer 1

7
$\begingroup$

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 improved assuming the Exponential Time Hypothesis. So, there is a brute-force quasi-polynomial time approach, but we don't expect to be able to improve it to get a polynomial-time algorithm.

$\endgroup$
4
  • 1
    $\begingroup$ I'm a noob so I could be wrong, but didn't the PY1996 paper just note there's an $n^{O(\log n)}$ algorithm, since one only needs to check if subsets of size at most $\lceil \log_2 n \rceil$ are shattered? $\endgroup$ Nov 6, 2021 at 14:46
  • $\begingroup$ Is the $n$ in your answer the cardinality of what I call $X$, or the cardinality of what I call $F$? $\endgroup$
    – Jack M
    Nov 7, 2021 at 8:57
  • $\begingroup$ @mathworker21 thanks you are right. I rephrased the answer to be clearer. $\endgroup$
    – Lev Reyzin
    Nov 7, 2021 at 14:48
  • $\begingroup$ @JackM here $n$ is the size of the input, which I take to be the number of entries in the input matrix. $\endgroup$
    – Lev Reyzin
    Nov 7, 2021 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.