  In this paper we apply methods originated in Complexity theory to some
problems of Approximation.
  We notice that the construction of Alman and Williams that disproves the
rigidity of Walsh-Hadamard matrices, provides good $\ell_p$-approximation for
$p<2$. It follows that the first $n$ functions of Walsh system can be
approximated with an error $n^{-\delta}$ by a linear space of dimension
$n^{1-\delta}$: $$ d_{n^{1-\delta}}(\{w_1,\ldots,w_n\}, L_p[0,1]) \le
n^{-\delta},\quad p\in[1,2),\;\delta=\delta(p)>0. $$ We do not know if this is
possible for the trigonometric system.
  We show that the algebraic method of Alon--Frankl--R\"odl for bounding the
number of low-signum-rank matrices, works for tensors: almost all
signum-tensors have large signum-rank and can't be $\ell_1$-approximated by
low-rank tensors. This implies lower bounds for $\Theta_m$~ -- the error of
$m$-term approximation of multivariate functions by sums of tensor products
$u^1(x_1)\cdots u^d(x_d)$. In particular, for the set of trigonometric
polynomials with spectrum in $\prod_{j=1}^d[-n_j,n_j]$ and of norm
$\|t\|_\infty\le 1$ we have $$ \Theta_m(\mathcal
T(n_1,\ldots,n_d)_\infty,L_1[-\pi,\pi]^d) \ge c_1(d)>0,\quad m\le
c_2(d)\frac{\prod n_j}{\max\{n_j\}}. $$ Sharp bounds follow for classes of
dominated mixed smoothness: $$
  \Theta_m(W^{(r,r,\ldots,r)}_p,L_q[0,1]^d)\asymp
m^{-\frac{rd}{d-1}},\quad\mbox 2\le p\le\infty,\; 1\le q\le 2. $$
