  A $k$-dimensional box is the Cartesian product $R_1 \times R_2 \times ...
\times R_k$ where each $R_i$ is a closed interval on the real line. The {\it
boxicity} of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$
such that $G$ can be represented as the intersection graph of a collection of
$k$-dimensional boxes. A unit cube in $k$-dimensional space or a $k$-cube is
defined as the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where
each $R_i$ is a closed interval on the real line of the form $[a_i,a_i + 1]$.
The {\it cubicity} of $G$, denoted as $\cub(G)$, is the minimum integer $k$
such that $G$ can be represented as the intersection graph of a collection of
$k$-cubes. The {\it threshold dimension} of a graph $G(V,E)$ is the smallest
integer $k$ such that $E$ can be covered by $k$ threshold spanning subgraphs of
$G$. In this paper we will show that there exists no polynomial-time algorithm
to approximate the threshold dimension of a graph on $n$ vertices with a factor
of $O(n^{0.5-\epsilon})$ for any $\epsilon >0$, unless $NP=ZPP$. From this
result we will show that there exists no polynomial-time algorithm to
approximate the boxicity and the cubicity of a graph on $n$ vertices with
factor $O(n^{0.5-\epsilon})$ for any $ \epsilon >0$, unless $NP=ZPP$. In fact
all these hardness results hold even for a highly structured class of graphs
namely the split graphs. We will also show that it is NP-complete to determine
if a given split graph has boxicity at most 3.
