Writing the unit $\ell_1$-ball in $\mathbb{R}^n$ as the intersection of closed half-spaces 
Check if $x \in \mathbb{R}^n$ satisfies $\|x\|_1\leq 1$ using linear methods only, that is, find $A \in \mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$ such that
$$Ax \leq b \Leftrightarrow x \in \overline{\mathbb{B}}_{(\mathbb{R}^n, \|\cdot\|_1)}$$
where $m$ is not exponentially dependent on $n$.

My straightforward solution, checking the sums $x_1+\dots+x_n$, $x=(x_1,\dots,x_n)$, with plus replaced by minus in all possible ways, against $b=(1,\dots,1)$, leads to $m=2^n$. Is there a way to do this in non-exponential time? Thanks in advance.
 A: As we discussed in the comments: it is not possible to express the $\ell_1$ norm ball without an exponential number of rows, unless you allow for additional variables.
The simplest approach is to introduce new variables $y_i$, $i=1,2,\dots, n$. Then you have:
\begin{array}{ll}
-x_i \leq y_i & i = 1,2,\dots,n \\
+x_i\leq y_i & i=1,2,\dots, n \\
\sum_i y_i \leq 1
\end{array}
So with $n$ additional variables you can express this with $2n+1$ inequalities. However, try and convince yourself that this still produces the same result:
\begin{array}{ll}
-x_i \leq y_i & i = 1,2,\dots,n \\
+x_i\leq y_i & i=1,2,\dots, n \\
\sum_i y_i = 1
\end{array}
All I have done is change the last inequality to an equation. If $\|x\|_1=1$, then this obviously holds, because the only valid values of $y$ are $y_i=|x_i|$. But it will work even if $\|x\|_1<1$; for instance, you can choose $y_i=|x_i|+\frac{1 - \|x\|_1}{n}$. Once you accept the validity of this system, then, you can eliminate one of the $y_i$ values:
\begin{array}{ll}
-x_i \leq y_i & i = 1,2,\dots,n-1 \\
+x_i\leq y_i & i=1,2,\dots, n-1 \\
-x_n\leq 1 - y_1 - y_2 - \dots - y_{n-1} \\
+x_n\leq 1 - y_1 -y_2 - \dots - y_{n-1}
\end{array}
So in fact, with $n-1$ additional variables we can express the norm ball with $2n$ inequalities.
