  The signaling dimension of any given physical system represents its classical
simulation cost, that is, the minimum dimension of a classical system capable
of reproducing all the input/output correlations of the given system. The
signaling dimension landscape is vastly unexplored; the only non-trivial
systems whose signaling dimension is known -- other than quantum systems -- are
the octahedron and the composition of two squares.
  Building on previous results by Matsumoto, Kimura, and Frenkel, our first
result consists of deriving bounds on the signaling dimension of any system as
a function of its Minkowski measure of asymmetry. We use such bounds to prove
that the signaling dimension of any two-dimensional system (i.e. with
two-dimensional set of admissible states, such as polygons and the real qubit)
is two if and only if such a set is centrally symmetric, and three otherwise,
thus conclusively settling the problem of the signaling dimension for such
systems.
  Guided by the relevance of symmetries in the two dimensional case, we propose
a branch and bound division-free algorithm for the exact computation of the
symmetries of any given polytope, in polynomial time in the number of vertices
and in factorial time in the dimension of the space. Our second result then
consist of providing an algorithm for the exact computation of the signaling
dimension of any given system, that outperforms previous proposals by
exploiting the aforementioned bounds to improve its pruning techniques and
incorporating as a subroutine the aforementioned symmetries-finding algorithm.
We apply our algorithm to compute the exact value of the signaling dimension
for all rational Platonic, Archimedean, and Catalan solids, and for the class
of hyper-octahedral systems up to dimension five.
