  Self-testing has been a rich area of study in quantum information theory. It
allows an experimenter to interact classically with a black box quantum system
and to test that a specific entangled state was present and a specific set of
measurements were performed. Recently, self-testing has been central to
high-profile results in complexity theory as seen in the work on entangled
games PCP of Natarajan and Vidick (FOCS 2018), iterated compression by
Fitzsimons et al. (STOC 2019), and NEEXP in MIP* due to Natarajan and Wright
(FOCS 2019).
  In this work, we introduce an algebraic generalization of CHSH by viewing it
as a linear constraint system (LCS) game, exhibiting self-testing properties
that are qualitatively different. These provide the first example of non-local
games that self-test non-Pauli operators resolving an open questions posed by
Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states
other than the maximally entangled state, and hence resolves the open question
posed by Cleve and Mittal (ICALP 2012). Additionally, our games have 1 bit
question and $\log n$ bit answer lengths making them suitable candidates for
complexity theoretic application. This work is the first step towards a general
theory of self-testing arbitrary groups. In order to obtain our results, we
exploit connections between sum of squares proofs, non-commutative ring theory,
and the Gowers-Hatami theorem from approximate representation theory. A crucial
part of our analysis is to introduce a sum of squares framework that
generalizes the \emph{solution group} of Cleve, Liu, and Slofstra (Journal of
Mathematical Physics 2017) to the non-pseudo-telepathic regime. Finally, we
give the first example of a game that is not a self-test. Our results suggest a
richer landscape of self-testing phenomena than previously considered.
