Eli Ben-Sasson, Michael Viderman

We continue the study of {\em robust} tensor codes and expand the

class of base codes that can be used as a starting point for the

construction of locally testable codes via robust two-wise tensor

products. In particular, we show that all unique-neighbor expander

codes and all locally correctable codes, ...
more >>>

Manuel Arora, GĂˇbor Ivanyos, Marek Karpinski, Nitin Saxena

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

Joseph Swernofsky

We prove that approximating the rank of a 3-tensor to within a factor of $1 + 1/1852 - \delta$, for any $\delta > 0$, is NP-hard over any finite field. We do this via reduction from bounded occurrence 2-SAT.

more >>>