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 >>>

We revisit a classical result of Coppersmith and Shparlinski [CS00] showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $\deg(f) \leq D$, we have:
$$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 ... more >>>