If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the data is linearly separable if and only if such a hyperplane exists.
If the data consists of $m$ pairs $(x_1, y_1), \ldots, (x_m,y_m)$, with $x_i \in \{0,1\}^n$ and $y_i \in \{0,1\}$, do we know what the worst case running time is for finding whether or not a maximum margin hyperlane exists?
Most of the work on SVM algorithms focuses on the soft-margin case and so isn't really applicable here.$\newcommand\R{\mathbb R}$
But the question of finding the existence of a linear separator can be solved instead as a linear program: Let $X_+$ be the matrix whose rows are the positive instances (the $x_i$ with $y_i = 1$), and $X_-$ the matrix whose rows are the negatives. Then our question is: is there a $\beta \in \R^n$ and $b \in \R$ such that $X_+ \beta > b$ and $X_- \beta < b$?
This is a linear feasibility problem in $n+1$ dimensions with $m$ linear constraints. Since your $X$ are binary, the LP can then be represented in $O(m n)$ bits; as an upper bound, Karmarkar's algorithm then runs in $$O(m^2 n^{5.5} \log(m n) \log(\log(m n)))$$ time.
Better bounds are certainly possible depending on the setting. For example, if the dimension $n$ is low, Megiddo (1984) gives an algorithm that takes fewer than $2^{2^{n+3}} m$ steps, or another which takes fewer than $\frac{2^{(n+1)^2}}{\prod_{k=1}^{n-1} k!} m (\log m)^{(n+1)^2}$.
