  We study the computational power of polynomial threshold functions, that is,
threshold functions of real polynomials over the boolean cube. We provide two
new results bounding the computational power of this model.
  Our first result shows that low-degree polynomial threshold functions cannot
approximate any function with many influential variables. We provide a couple
of examples where this technique yields tight approximation bounds.
  Our second result relates to constructing pseudorandom generators fooling
low-degree polynomial threshold functions. This problem has received attention
recently, where Diakonikolas et al proved that $k$-wise independence suffices
to fool linear threshold functions. We prove that any low-degree polynomial
threshold function, which can be represented as a function of a small number of
linear threshold functions, can also be fooled by $k$-wise independence. We
view this as an important step towards fooling general polynomial threshold
functions, and we discuss a plausible approach achieving this goal based on our
techniques.
  Our results combine tools from real approximation theory, hyper-contractive
inequalities and probabilistic methods. In particular, we develop several new
tools in approximation theory which may be of independent interest.
