The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, i.e.\ a noncommutative arithmetic circuit that has inversion gates, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time \cite{GGOW20}, \cite{IQS18}. For rational circuits of ... more >>>

Bhangale, Khot, and Minzer (TheoretiCS 2026) proposed a hybrid approximation algorithm for certain satisfiable CSPs to exploit their abelian embeddings. We propose BasicSDP $\wedge$ CSinglAIP to simplify and generalize their hybrid algorithm. We do so by introducing two concepts:
(1) universal embedding, which simplifies and generalizes their master embedding, and
more >>>

The question of whether the Gilbert-Varshamov bound (1952, 1957) gives the optimal tradeoff between rate and distance is one of the most fundamental in coding theory. It is a central instance of the broader question of how far algebraic structure can surpass the benchmark provided by the probabilistic method.

In ... more >>>