<p>In 1996 Papadimitriou and Yannakakis <a href="https://www.sciencedirect.com/science/article/pii/S0022000096900586?via%3Dihub" rel="nofollow noreferrer">noted</a> that there exists an <span class="math-container">$n^{O(\log n)}$</span> brute-force algorithm (where <span class="math-container">$n$</span> 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.</p>
<p>Manurangsi and Rubinstein later <a href="http://proceedings.mlr.press/v65/manurangsi17a/manurangsi17a.pdf" rel="nofollow noreferrer">showed</a> 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.</p>

CC BY-SA 4.0
2021-11-06T14:46:33.353Z
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?
mathworker21
CC BY-SA 4.0
2021-11-07T08:57:48.310Z
Is the $n$ in your answer the cardinality of what I call $X$, or the cardinality of what I call $F$?
Jack M
CC BY-SA 4.0
2021-11-07T14:48:58.647Z
@mathworker21 thanks you are right. I rephrased the answer to be clearer.
Lev Reyzin
CC BY-SA 4.0
2021-11-07T14:49:31.643Z
@JackM here $n$ is the size of the input, which I take to be the number of entries in the input matrix.
Lev Reyzin
CC BY-SA 4.0
2021-11-05T21:44:36.717Z
2021-11-07T14:57:17.547Z
2021-11-07T14:57:17.547Z
Lev Reyzin
<p>Let <span class="math-container">$F$</span> be a class of subsets of a finite set <span class="math-container">$X$</span> of cardinality <span class="math-container">$n$</span>. What is the complexity of computing the VC dimension of <span class="math-container">$F$</span>? Can we do better than looping through every subset of <span class="math-container">$X$</span> and checking if <span class="math-container">$F$</span> shatters it?</p>

<ds.algorithms><co.combinatorics><vc-dimension>
How can we compute the VC dimension of a finite class of sets?
Jack M
# How can we compute the VC dimension of a finite class of sets?

(Asked by: username_0 on 2021-11-05)

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?

**Tags:** ds.algorithms, co.combinatorics, vc-dimension


---

## 1 answers

### Answer by username_1 on 2021-11-05. Score: 7 | Accepted answer

In 1996 Papadimitriou and Yannakakis [noted](https://www.sciencedirect.com/science/article/pii/S0022000096900586?via%3Dihub) 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](http://proceedings.mlr.press/v65/manurangsi17a/manurangsi17a.pdf) 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.

> **Comments:**
> **username_2**: 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?  
> **username_0**: Is the $n$ in your answer the cardinality of what I call $X$, or the cardinality of what I call $F$?  
> **username_1**: @username_2 thanks you are right. I rephrased the answer to be clearer.  
> **username_1**: @JackM here $n$ is the size of the input, which I take to be the number of entries in the input matrix.  

---

