It is usually said that existence of discrete spacetime violates Lorentz symmetry. What quantity is used to quantify such violation? I mean could someone points a reference for a derivation that shows such analysis.
My other question is: if Lorentz symmetry is violated, does that imply space-time is discrete? or not necessarily?)
There are nontrivial discrete subgroups of the Lorentz group. It is easy to construct an SO(3,1) matrix that has only integer entries and yet is not just a simple rotation. A rectangular lattice in Minkowski space is invariant under the group of these transformations. Different space-time lattices have different discrete subgroups of Lorentz under which they are invariant.
This might be what you are looking for, even if it does not answer the question ...
However, there is a snag: it is extremely difficult to construct any non-trivial dynamical model of nature (quantum, classical, anything) that transforms into itself under these discrete transformations, even if their lattice does. Versions of string theory, adapted to this lattice, may give you the best promises.
So my advice is: don't believe the no-go theorems.
The analysis of Lorentz violations is found in Coleman and Glashow's "High Energy Tests of Lorentz Invariance": http://arxiv.org/abs/hep-ph/9812418 .
The discreteness leads to Lorentz-violation arguments turn out to be bogus in light of holography (in this I believe I completely agree with t'Hooft), they assume that the symmetry of the space time has to be a symmetry of the space-time points. When the bulk is emergent, even if the boundary is discrete, the emergent symmetry in most of the bulk can be as good as the longest-wavelengths of the boundary theory, so that it is essentially exact.
This is the reason that discrete theories are viable, but only in light of holography. If you make a naive lattice at the Planck scale, say, you break Lorentz invariance by too much. I'll defer to the linked paper for precise bounds, I don't know them.
