Are there known algorithms for the following problem that beat the naive algorithm?
Input: A system $Ax \le b$ of $m$ linear inequalities.
Output: A feasible solution $x^*\in \{0,1 \}^n$ if one exists.
Assume that $A$ and $b$ have integer entries. I'm interested in worst-case bounds.
If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.
However, there is an algorithm due to Impagliazzo, Paturi, and myself that can solve such a system of inequalities if the number of wires, i.e. the number of nonzero coefficients in $A$ is linear. In particular, if the number of wires is $cn$, the algorithm runs in time $2^{(1-s)n}$, where $s=\frac1{c^{O(c^2)}}$.
If $m$ is small enough, you can do better than the naive algorithm, i.e., better than $2^n$ time. Here "small enough" means that $m$ is smaller than something like $n/\lg n$. The running time will still be exponential -- e.g., it might be $2^{n/2}$ time -- but it'll be faster than the naive algorithm.
Incidentally, it looks like this does allow us to solve the problem in faster than $2^n$ time for some cases where the matrix $A$ has a super-linear number of entries. I don't know how to square that with the other answer provided here. Consequently, you should check my answer carefully: it might indicate that I have made a serious mistake somewhere.
The basic approach: write $x=(x_0,x_1)$, where $x_0$ holds the first $n/2$ components of $x$ and $x_1$ holds the last $n/2$ components; and similarly $A=(A_0,A_1)$, where $A_0$ has the left $n/2$ columns of $A$ and $A_1$ the right $n/2$ columns. Now $Ax \le b$ can be re-written in the form
$$A_0 x_0 + A_1 x_1 \le b,$$
or equivalently,
$$A_0 x_0 \le b - A_1 x_1.$$
Enumerate all $2^{n/2}$ possibilities for $A_0 x_0$, and let $S$ denote the set of possible values, i.e.,
$$S=\{A_0 x_0 : x_0 \in \{0,1\}^{n/2}\}.$$
Similarly, enumerate the set $T$ of all $2^{n/2}$ possibilities for $b - A_1 x_1$, i.e.,
$$T = \{b - A_1 x_1 : x_1 \in \{0,1\}^{n/2}\}.$$
Now the problem becomes
Given sets $S,T \subseteq \mathbb{Z}^{m}$ of size $2^{n/2}$, does there exist $s\in S$ and $t \in T$ such that $s\le t$?
(Here $\le$ is taken pointwise, i.e., we require that $s_i \le t_i$ for all $i$.)
The latter problem is discussed on CS.StackExchange, and there is apparently an algorithm for it that runs in time $O(2^{n/2} (n/2)^{m-1})$. If $m$ is sufficiently small (say, smaller than $n/\lg n$), then it follows that the total running time will be less than $2^n$, as desired.
To help make this result sound more plausible, here's some very crude intuition. If we take the extreme case where $m=1$, of course this can be solved quickly. (There's actually a much simpler algorithm for the special case where $m=1$: let $x_i=1$ if $A_{1,i}\le 0$, otherwise $x_i=0$; now if any feasible solution exists, then this $x$ will be one.)
