We prove a stability result for general $3$-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if $\Sigma,\Gamma$ and $\Phi$ are alphabets of constant size, and $\mu$ is a pairwise connected distribution over $\Sigma\times\Gamma\times\Phi$ with no $(\mathbb{Z},+)$ embeddings in which the probability of each atom is ... more >>>

We give a conversion from non-classical polynomials to $\mathit{MidBit}^+$ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and $\mathit{MidBit}^+$ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three ... more >>>

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With ... more >>>